using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.IO;

namespace MazeSolver
{

/// <summary>
/// Solveur de labyrinthe par Pascal Boutin
/// </summary>

    class Program
    {
        struct Coord
        {
            public int x;
            public int y;
        }

        struct Orientation
        {
            public bool north;
            public bool east;
            public bool south;
            public bool west;
        }

        struct PosLab
        {
            public Coord Position;
            public Orientation Orient;
        }

        static void Main(string[] args)
        {
            // Dimensions du labyrinthe
            const int xMax = 70;
            const int yMax = 20;

            // Structures de données
            Stack LabIntersect = new Stack();   // Contient les intersections
            ArrayList History = new ArrayList();

            // Fichier
            StreamReader file = new StreamReader("laby.txt");

            // Tableaux
            string [] MazeMap = new string[yMax];   // Contient la map
            bool[,] MazeResult;                     // Va contenir la solution

            // Variables
            bool finish = false;                // Indique si la résolution est finit
            bool resolved = false;                      // Indique si le labyrinthe est résolu
            int NbPoss;                         // Indique le nombre de possibilités de déplacements
            string way = "";                        // Indique par ou je vais
            PosLab CurrentPos = new PosLab();   // Position courante

            Random rndpos = new Random();

            for ( int i = 0; i < yMax; i++ )
                // Charger le fichier et trouver la position courante
            {
                MazeMap[i] = file.ReadLine();

                // Si on trouve l'entrée, on stocke les coordonnées dans la position courante
                if (MazeMap[i].IndexOf('E') != 0)
                {
                    CurrentPos.Position.x = MazeMap[i].IndexOf('E');
                    CurrentPos.Position.y = i;
                }
                i++;
            }

            // Résolution du labyrinthe
            while (!finish)
            {
                // Vérifier si on on peux se déplacer dans chaque direction et si on est dans les limites
                if (CurrentPos.Position.y == 0) CurrentPos.Orient.north = false; else CurrentPos.Orient.north = (MazeMap[CurrentPos.Position.y - 1][CurrentPos.Position.x] == '1');

                if (CurrentPos.Position.x == xMax) CurrentPos.Orient.east = false; else CurrentPos.Orient.east = (MazeMap[CurrentPos.Position.y][CurrentPos.Position.x + 1] == '1');

                if (CurrentPos.Position.y == yMax) CurrentPos.Orient.south = false; else CurrentPos.Orient.south = (MazeMap[CurrentPos.Position.y + 1][CurrentPos.Position.x] == '1');

                if (CurrentPos.Position.x == 0) CurrentPos.Orient.west = false; else CurrentPos.Orient.west = (MazeMap[CurrentPos.Position.y][CurrentPos.Position.x - 1] == '1');

                // Éviter de revenir sur ses pas
                switch (way)
                {
                    case "n": CurrentPos.Orient.south = false;
                        break;
                    case "e": CurrentPos.Orient.west = false;
                        break;
                    case "s": CurrentPos.Orient.north = false;
                        break;
                    case "w": CurrentPos.Orient.east = false;
                        break;
                }

                History.Add(CurrentPos);

            Depile:

                // Trouver le nombre de possibilités
                way = "";

                if (CurrentPos.Orient.north) way = way + "n";
                if (CurrentPos.Orient.east) way = way + "e";
                if (CurrentPos.Orient.south) way = way + "s";
                if (CurrentPos.Orient.west) way = way + "w";

                NbPoss = way.Length;

                // Choix aléatoire de la direction à emprunter
                way = way[rndpos.Next(1, NbPoss)].ToString();


                // Si on a pas de possibilitées
                if (NbPoss == 0)
                {
                    // Et que la pile est vide
                    if (LabIntersect.Count == 0)
                    {
                          finish = true;
                          resolved = false;
                     }
                        // sinon de dépile
                     else
                     {
                          CurrentPos = (PosLab)LabIntersect.Pop();

                          History.RemoveRange(History.IndexOf(CurrentPos) + 1, History.Count - History.IndexOf(CurrentPos));

                        // Pour contourner l'évaluation des possibilités
                          goto Depile;
                     }
                }

                else
                {
                    if (NbPoss > 1)
                    {
                        switch (way)
                        {
                            case "n":
                                {
                                    CurrentPos.Orient.north = false;
                                }
                                break;

                            case "e":
                                {
                                    CurrentPos.Orient.east = false;
                                }
                                break;

                            case "s":
                                {
                                    CurrentPos.Orient.south = false;
                                }
                                break;

                            case "w":
                                {
                                    CurrentPos.Orient.west = false;
                                }
                                break;
                        }

                        LabIntersect.Push(CurrentPos);
                    }

                      switch (way)
                      {
                                case "n":
                                    {
                                        CurrentPos.Position.y = CurrentPos.Position.y - 1;
                                    }
                                    break;

                                case "e":
                                    {
                                        CurrentPos.Position.x = CurrentPos.Position.x + 1;
                                    }
                                    break;

                                case "s":
                                    {
                                        CurrentPos.Position.y = CurrentPos.Position.y + 1;
                                    }
                                    break;

                                case "w":
                                    {
                                        CurrentPos.Position.x = CurrentPos.Position.x - 1;
                                    }
                                    break;
                       }
                }

            }

            // Écrit la solution dans un tableau de booléen
            for (int i = 0; i < History.Count; i++)
            {
                History[i

            }


            if (resolved)
            {
                System.Console.WriteLine("Le labyrinthe est résolu !");
            }
            else
            {
                System.Console.WriteLine("C'est impossible !!!");
            }


         }




     }
}