Problem Link - Medu Vada Maze
Problem Statement
A maze, for our purposes, consists of a rectangular grid of cells, where some of the cells are blocked and the remaining cells are empty. A mouse is placed in one of the empty cells and a dosa is placed at a different empty cell. From a cell, the mouse can move to any empty neighbouring cell according to the rules given below. Your aim is to determine whether the mouse can walk through this maze and reach the dosa.
A maze with R rows and C columns will be presented as a sequence of R lines, each with C characters. The character # denotes a blocked cell and the character . denotes an empty cell). The mouse and the dosa sit in distinct empty cells and those cells are marked by M and D instead of .
Approach
The problem is solved using Depth First Search (DFS) to explore all possible paths the mouse can take from its starting position (M) to the target (D). A grid of visited cells is maintained to avoid revisiting the same cell. Additionally, a par array is used to track the parent of each cell, allowing the reconstruction of the path.
During the DFS, whenever the mouse tries to move out of bounds, the coordinates are adjusted to simulate the wrapping behavior of the grid. If the mouse reaches the dosa, it indicates that the path exists. After finding the path, the par array is used to backtrack and mark the path from M to D in the grid. Finally, the modified grid is printed, showing the path marked with an x. If the dosa is unreachable, the program outputs NO.
Time Complexity
The time complexity is O(n \times m), where n and m are the dimensions of the grid, as every cell is visited at most once during the DFS.
Space Complexity
The space complexity is O(n \times m) for the vis and par arrays, plus the recursive stack, which can also go up to O(n \times m) in the worst case.