Day3Maze

using System;

namespace BacktrackingMaze
{
    class Program
    {

        static char[,] lab1 =
        {
            { ' ', ' ', ' ', ' ' },
            { ' ', '*', ' ', ' ' },
            { 'f', ' ', ' ', 'f' }
        };

        static char[,] lab =
        {
            { ' ', ' ', ' ', '*', ' ', ' ', ' ' },
            { '*', '*', ' ', '*', ' ', '*', ' ' },
            { ' ', ' ', ' ', ' ', ' ', ' ', ' ' },
            { ' ', '*', '*', '*', '*', '*', ' ' },
            { ' ', ' ', ' ', ' ', ' ', ' ', 'f' },
        };

        static void FindPath(int row, int col)
        {
            if (row < 0 || col < 0 || row >= lab.GetLength(0) || col >= lab.GetLength(1) || lab[row, col] == 'v')
            {
                // we are out of labyrinth
                return;
            }

            if (lab[row, col] == 'f')
            {
                Console.WriteLine("Found path!");
            }

            if (lab[row, col] == ' ')
            {
                lab[row, col] = 'v';
                FindPath(row, col - 1);
                FindPath(row - 1, col);
                FindPath(row, col + 1);
                FindPath(row + 1, col);
                lab[row, col] = ' ';
            }
        }


        static char[] path = new char[lab.GetLength(0) * lab.GetLength(1)];
        static int position = 0;
        static void FindPath(int row, int col, char direction)
        {
            // out of lab
            if((col < 0) || (row < 0) || (col >= lab.GetLength(1)) || (row >= lab.GetLength(0)))
            {
                return;
            }

            path[position] = direction;
            position++;

            if (lab[row, col] == 'e')
            {
                PrintPath(path, 0, position - 1);
            }

            if (lab[row, col] == ' ')
            {
                lab[row, col] = 's';

                FindPath(row, col - 1, 'L');
                FindPath(row - 1, col, 'U');
                FindPath(row, col + 1, 'R');
                FindPath(row + 1, col, 'D');

                // mark as free
                lab[row, col] = ' ';
            }
            position--;
        }

        static void PrintPath(char[] path, int startPos, int endPos)
        {
            Console.Write("Found path to the exit: ");
            for (int pos = startPos; pos <= endPos; pos++)
            {
                Console.Write(path[pos]);
            }
            Console.WriteLine();
        }

        static void Main(string[] args)
        {
            FindPath(0, 0);
            //FindPath(0, 0, 'S');
        }
    }
}