maze - backtracking

namespace prolazak_kroz_lavirint___backtracking
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[,] maze = new string[,]
            {
                { "", "X", "X", "X", "X" },
                { "", "X",  "",  "",  "" },
                { "",  "",  "",  "",  "" },
                { "", "X",  "", "X",  "" },
            };

            int xStart = 1;
            int yStart = 0;

            int xEnd = 2;
            int yEnd = 4;


            int[,] moves = new int[,]
            {
                {-1, 0 },   //left
                {0, -1 },   //up
                {1, 0 },    //right
                {0, 1 },    //down
            };

            maze[xStart, yStart] = ".";

            bool gotOut = false;

            //GetOutOfTheMaze(maze, moves, xStart, yStart, xEnd, yEnd, ref gotOut);//first solution, not fastest

            int numSteps = 0;
            int minSteps = int.MaxValue;
            //string[,] shortestSolution = new string[,];

            GetOutOfTheMazeShortest(maze, moves, xStart, yStart, xEnd, yEnd, numSteps, ref minSteps);
        }

        private static void GetOutOfTheMaze(string[,] maze, int[,] moves, int x, int y, int xEnd, int yEnd, ref bool gotOut)
        {
            if (x == xEnd && y == yEnd)
            {
                outputMatrix(maze);
                gotOut = true;
                return;
            }


            for (int i = 0; i <= moves.GetLength(0) - 1; i++)
            {
                int newX = x + moves[i, 0];
                int newY = y + moves[i, 1];


                if (ValidMove(newX, newY, maze) && !gotOut)
                {
                    maze[newX, newY] = ".";//add new move

                    GetOutOfTheMaze(maze, moves, newX, newY, xEnd, yEnd, ref gotOut);

                    maze[newX, newY] = "";//erase that(new) move

                }
            }


        }

        private static void GetOutOfTheMazeShortest(string[,] maze, int[,] moves, int x, int y, int xEnd, int yEnd, int numSteps, ref int minSteps)
        {
            if (x == xEnd && y == yEnd)
            {
                if (minSteps < numSteps)
                {
                    outputMatrix(maze);
                    minSteps = numSteps;
                }

                return;
            }


            for (int i = 0; i <= moves.GetLength(0) - 1; i++)
            {
                int newX = x + moves[i, 0];
                int newY = y + moves[i, 1];


                if (ValidMove(newX, newY, maze))
                {
                    maze[newX, newY] = ".";//add new move

                    GetOutOfTheMazeShortest(maze, moves, newX, newY, xEnd, yEnd);

                    maze[newX, newY] = "";//erase that(new) move

                }
            }


        }


        private static bool ValidMove(int newX, int newY, string[,] maze)
        {
            return newX >= 0 && newX <= maze.GetLength(0) - 1 && newY >= 0 && newY <= maze.GetLength(1) - 1 && maze[newX, newY] == "";
        }

        private static void outputMatrix(string[,] maze)
        {
            for (int i = 0; i <= maze.GetLength(0) - 1; i++)
            {
                for (int j = 0; j <= maze.GetLength(1) - 1; j++)
                {
                    Console.Write(maze[i, j].PadLeft(2));
                }
                Console.WriteLine();
            }

            Console.WriteLine();
        }

    }
}