using System;
using System.Collections.Generic;
using System.Linq;

namespace Program
{
    public struct Cord
    {
        public int X { get; set; }
        public int Y { get; set; }
        public static readonly Cord Up = new Cord { X = 0, Y = -1 };
        public static readonly Cord Down = new Cord { X = 0, Y = 1 };
        public static readonly Cord Left = new Cord { X = -1, Y = 0 };
        public static readonly Cord Right = new Cord { X = 1, Y = 0 };
    }

    public class City
    {
        public int Width { get; private set; }
        public int Height { get; private set; }
        public int Prefered { get; private set; }
        public bool[,] NotPassable { get; private set; }

        public City(int width, int height, int prefered)
        {
            NotPassable = new bool[width, height];
        }

        private static readonly Cord[][] PreferedNeigbors = new Cord[][]
        {
            new Cord[] { Cord.Up, Cord.Down, Cord.Left, Cord.Right },
            new Cord[] { Cord.Right, Cord.Left, Cord.Down, Cord.Up },
            new Cord[] { Cord.Left, Cord.Up, Cord.Down, Cord.Right },
            new Cord[] { Cord.Down, Cord.Right, Cord.Up, Cord.Left },
        };

        private IEnumerable<Cord> GetNeigbors(Cord cord)
        {
            return PreferedNeigbors[Prefered]
                 .Select((n) => new Cord { X = n.X + cord.X, Y = n.Y + cord.Y })
                 .Where((n) => n.X > 0 && n.Y > 0 && n.X < Width && n.Y < Height);
        }

        private class QueueNode
        {
            public Cord Cord { get; set; }
            public QueueNode LastNode { get; set; }
        }

        public List<Cord> GetPath(Cord start, Cord end)
        {
            var path = new List<Cord>();
            var queue = new Queue<QueueNode>();
            var visited = new bool[Width, Height];

            queue.Enqueue(new QueueNode
            {
                Cord = start,
                LastNode = null,
            });

            while(queue.Count != 0)
            {
                var current = queue.Dequeue();

                if(current.Cord.X == end.X && current.Cord.Y == end.Y)
                {
                    for(var n = current; n != null; n = n.LastNode)
                    {
                        path.Append(n.Cord);
                    }
                    break;
                }
                foreach(var n in GetNeigbors(current.Cord))
                {
                    if(!visited[n.X, n.Y] && !NotPassable[n.X, n.Y])
                    {
                        visited[n.X, n.Y] = true;
                        queue.Enqueue(new QueueNode
                        {
                            Cord = current.Cord,
                            LastNode = current,
                        });
                    }
                }
            }

            return path;
        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
        }
    }
}