using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp4
{

    public class Edge
    {
        public readonly Node From;
        public readonly Node To;
        public Edge(Node first, Node second)
        {
            this.From = first;
            this.To = second;
        }//Инцидентность ребра вершине
        public bool IsIncident(Node node)
        {
            return From == node || To == node;
        }// если имеется вершина, то возвращается инцидентная ей
        public Node OtherNode(Node node)
        {
            if (!IsIncident(node)) throw new ArgumentException();
            if (From == node) return To;
            return From;
        }
    }

    public class Node
    {
        readonly List<Edge> edges = new List<Edge>();//Нумерация
        public readonly int NodeNumber;

        public Node(int number)
        {
            NodeNumber = number;
        }
        // Св-во позволяющее перечислить все вершины, инцидентные ребру
        public IEnumerable<Node> IncidentNodes
        {
            get
            {
                return edges.Select(z => z.OtherNode(this));
            }
        }// перечисление всех ребер, инцидентных данной вершине
        public IEnumerable<Edge> IncidentEdges
        {
            get
            {
                foreach (var e in edges) yield return e;
            }
        }
        public static Edge Connect(Node node1, Node node2, Graph graph)
        {//Чтобы не было возможности присоединить к графу новую вершину, не лежащую в графе
            if (!graph.Nodes.Contains(node1) || !graph.Nodes.Contains(node2)) throw new ArgumentException();
            var edge = new Edge(node1, node2);// создание ребра,соед-го две вершины
            node1.edges.Add(edge);// добавление ребра  в коллекцию для каждой вершины
            node2.edges.Add(edge);
            return edge;
        }
        public static void Disconnect(Edge edge) // удаление ребра
        {
            edge.From.edges.Remove(edge);
            edge.To.edges.Remove(edge);
        }
    }


    public class Graph
    {
        private Node[] nodes;
        // дание графа
        public Graph(int nodesCount)
        {
            nodes = Enumerable.Range(0, nodesCount).Select(z => new Node(z)).ToArray();
        }

        public int Length { get { return nodes.Length; } }
        // индексация
        public Node this[int index] { get { return nodes[index]; } }
        // список всез вершин в графе
        public IEnumerable<Node> Nodes
        {
            get
            {
                foreach (var node in nodes)
                    yield return node;
            }
        }

        public void Connect(int index1, int index2)
        {
            Node.Connect(nodes[index1], nodes[index2], this);
        }
        // удаление ребра
        public void Delete(Edge edge)
        {
            Node.Disconnect(edge);
        }
        // перечисление всех ребер графа
        public IEnumerable<Edge> Edges
        {
            get
            {
                return nodes.SelectMany(z => z.IncidentEdges).Distinct();
            }
        }

        public static Graph MakeGraph(params int[] incidentNodes) // создает граф
        {
            var graph = new Graph(incidentNodes.Max() + 1);
            for (int i = 0; i < incidentNodes.Length - 1; i += 2)
                graph.Connect(incidentNodes[i], incidentNodes[i + 1]);
            return graph;
        }

        public static int[,] MakeMatrix(string[] labyrinth)
        {
            var incidents = new int[labyrinth.Length, labyrinth[0].Length];// делаем матрица, если участок пустой, то помечаем его как "1", иначе как "0"
            for (int i = 0; i < labyrinth.Length; i++)
                for (int j = 0; j < labyrinth[i].Length; j++)
                {
                    if (labyrinth[i][j] == ' ')
                    {
                        incidents[i, j] = 1;
                    }
                    else
                        incidents[i, j] = 0;
                }
            return incidents;
        }
    }

    public static class Program
    {
        public static IEnumerable<Node> FindShortestPath(this Graph graph, Node start, Node end)
        {
            var track = new Dictionary<Node, Node>();
            var queue = new Queue<Node>();
            queue.Enqueue(start);
            track[start] = null; // стартовая вершина
            while (queue.Count != 0)
            {
                var node = queue.Dequeue();
                track.ContainsKey(node);
                bool endIsFound = false;
                foreach (var nextNode in node.IncidentNodes)
                {
                    if (track.ContainsKey(nextNode)) continue;
                    track[nextNode] = node;// кратчайший путь в некстнод из НОД
                    queue.Enqueue(nextNode);
                    if (nextNode == end) endIsFound = true;
                }
                if (endIsFound) break;
            }
            if (!track.ContainsKey(end)) return null; // проверка на связность графа
            var list = new List<Node>();
            while (end != null)
            {
                list.Add(end);
                end = track[end]; // движение по массиву из конца в начало
            }
            list.Reverse();
            return list;
        }

        public static List<int> TransformToGraph(int[,] arr)
        {
            var list = new List<int>();
            for (int i = 0; i < arr.GetLength(0); i++)
            {
                for (int j = 0; j < arr.GetLength(1); j++)
                {
                    if (arr[i, j] == 1)
                    {
                        // TO DO
                    }
                }
            }
            return list;
        }

        static void Main(string[] args)
        {
            string[] labyrinth = new string[]
            {
                "X     XXXX",
                "XX XX XX X",
                "XX     X  ",
                "XX X XXX X",
                "X        X",
                "X  X XX  X",
                "XXXX      ",
            };


            var arr = Graph.MakeMatrix(labyrinth);
            var matrix = TransformToGraph(arr).ToArray();
            var graph = Graph.MakeGraph(0, 1, 1, 2, 1, 5, 2, 3, 3, 4, 4, 6, 5, 8, 6, 11, 8, 9, 9, 10, 10, 11, 11, 12, 8, 15, 10, 16, 13, 7, 13, 14, 17, 13,
                15, 19, 16, 21, 17, 25, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 18, 26, 19, 27, 21, 28, 24, 29, 25, 30, 26, 27, 29, 30, 28,
                31, 29, 34, 30, 35, 31, 32, 32, 33, 33, 34, 34, 35, 35, 36);
            foreach (var node in graph.FindShortestPath(graph[0], graph[36]))
                Console.WriteLine(node.NodeNumber);
            Console.ReadKey();
        }
    }
}