using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Security.Permissions;

namespace KnightAndPawn
{
    public class Point
    {
        public int X
        {
            get; private set;
        }

        public int Y
        {
            get; private set;
        }

        public Point(int x, int y)
        {
            X = x;
            Y = y;
        }

        public override string ToString()
        {
            return Program.ConvertFromPointToString(this);

        }

        public override bool Equals(object obj)
        {
            if (obj.GetType() != typeof (Point))
                return false;
            var oth = (Point) obj;
            return oth.X == X && oth.Y == Y;
        }

        public override int GetHashCode()
        {
            return new System.Drawing.Point(X, Y).GetHashCode();
        }
    }

    public class Program
    {
        public static string ConvertFromPointToString(Point point)
        {
            var dict = new Dictionary<int, string>{
                {0, "a"}, {1,"b"}, {2, "c"}, {3, "d"},
                {4, "e"}, {5, "f"}, {6, "g"}, {7, "h"}
            };
            return dict[point.X] + (point.Y + 1).ToString();

        }

        public static Point GetCooFromString(string input)
        {
            var dict = new Dictionary<string, int>{
                {"a", 0}, {"b", 1}, {"c", 2}, {"d", 3},
                {"e", 4}, {"f", 5}, {"g", 6}, {"h", 7}
            };
            var x = dict[input.First().ToString()];
            var y = int.Parse(input.Last().ToString()) - 1;
            return new Point(x, y);
        }

        public static bool CheckBounds(Point currentPoint)
        {
            return currentPoint.X >= 0 && currentPoint.X < 8 &&
                currentPoint.Y >= 0 && currentPoint.Y < 8;
        }

        public static bool IsUnderAttack(Point point, Point pawn)
        {
            var firstPosition = new Point(pawn.X + 1, pawn.Y - 1);
            var secondPosition = new Point(pawn.X - 1, pawn.Y - 1);
            return Equals(point, firstPosition) || Equals(point, secondPosition);
        }

        public static IEnumerable<Point> GetNeighbours(Point currentPoint)
        {
            var vectors = new List<Point>{
                new Point(1, 2), new Point(-1, 2),
                new Point(-2, 1), new Point(-2, -1),
                new Point(-1, -2), new Point(1, -2),
                new Point(2, -1), new Point(2, 1)
            };

            return vectors
                .Select(vect => new Point(vect.X + currentPoint.X, vect.Y + currentPoint.Y))
                .Where(CheckBounds);
        }

        public static Tuple<Point, Point> GetCooFromFile()
        {
            var lines = File.ReadAllLines(@".\in.txt");
            var knight = GetCooFromString(lines[0]);
            var pawn = GetCooFromString(lines[1]);
            return Tuple.Create(knight, pawn);
        }
        public static void Main(string[] args)
        {
            var parents = new Point[8,8];
            var input = GetCooFromFile();
            var knight = input.Item1;
            var pawn = input.Item2;
            var visited = new List<Point>();

            var stack = new Stack<Point>();
            stack.Push(knight);
            while (true)
            {
                var current = stack.Pop();
                if (visited.Contains(current))
                    continue;
                visited.Add(current);
                if (current.Equals(pawn))
                    break;
                var flag = false;
                foreach (var nei in GetNeighbours(current))
                {
                    if (parents[nei.X, nei.Y] != null)
                        continue;
                    if (!visited.Contains(nei) && !IsUnderAttack(nei, pawn))
                    {
                        parents[nei.X, nei.Y] = current;
                        stack.Push(nei);
                    }
                    if (!Equals(nei, pawn)) continue;
                    flag = true;
                    break;
                }
                if (flag)
                    break;

            }
            var path = new List<Point>();
            var currentPoint = pawn;
            while (!Equals(currentPoint, knight))
            {
                path.Add(currentPoint);
                currentPoint = parents[currentPoint.X, currentPoint.Y];
            }
            path.Add(knight);
            path.Reverse();
            string answer = path.Aggregate("", (current, p) => current + (ConvertFromPointToString(p) + "\r\n"));
            File.WriteAllText(@".\out.txt", answer);
        }
    }
}