The symbol ’e’ is the exit (can occur multiple times)
staticvoidFindExit(int row, int col)
{
if ((col < 0) || (row < 0) || (col >= lab.GetLength(1))
|| (row >= lab.GetLength(0)))
{
// We are out of the labyrinth -> can't find a pathreturn;
}
// Check if we have found the exitif (lab[row, col] == 'е')
{
Console.WriteLine("Found the exit!");
}
if (lab[row, col] != ' ')
{
// The current cell is not free -> can't find a pathreturn;
}
// (example continues)
// Temporary mark the current cell as visited
lab[row, col] = 's';
// Invoke recursion to explore all possible directions
FindExit(row, col-1); // left
FindExit(row-1, col); // up
FindExit(row, col+1); // right
FindExit(row+1, col); // down// Mark back the current cell as free
lab[row, col] = ' ';
}
staticvoidMain()
{
FindExit(0, 0);
}
Find All Paths and Print Them
How to print all paths found by our recursive algorithm?
Each move’s direction can be stored in a list
Need to pass the movement direction at each recursive call (L, R, U, or D)
At the start of each recursive call the current direction is appended to the list
At the end of each recursive call the last direction is removed from the list
static List<char> path = new List<char>();
staticvoidFindPathToExit(int row, int col, char direction)
{
...
// Append the current direction to the path
path.Add(direction);
if (lab[row, col] == 'е')
{
// The exit is found -> print the current path
}
...
// Recursively explore all possible directions
FindPathToExit(row, col - 1, 'L'); // left
FindPathToExit(row - 1, col, 'U'); // up
FindPathToExit(row, col + 1, 'R'); // right
FindPathToExit(row + 1, col, 'D'); // down
...
// Remove the last direction from the path
path.RemoveAt(path.Count - 1);
}
Recursion Can be Harmful!
When used incorrectly the recursion could take too much memory and computing power