Rat in a Maze Problem in Java
In this section, we will discuss the rat in a maze problem in Java. The rat in a maze problem is one of the famous backtracking problems asked in the interviews.
Problem Statement: A maze is provided in the form R * C matrix, where R is the total number of rows, and C is the total number of columns present in the matrix (R may or may not become equal to C). The cell m[0][0] is the source (observe the following diagram). From the source, the rat starts its journey. The rat has to reach cell m[R – 1][C – 1], the destination cell. The rat can only move in the rightward (→) or in the downward (↓) direction from the cell where it is currently present. Also, note that the rat can only move to its adjacent cell. For example from the cell m[0][0], it can move to m[0][1] or m[1][0]. From m[0][0] it cannot move to m[0][2] or m[2][0] directly as cells m[0][2] or m[2][0] is not adjacent to m[0][0].
The following is the binary representation of the mentioned maze.
Here, 0 means that the cell is open, and the rat can enter. 1 means the cell is blocked, and the rat cannot enter.
The following diagram shows the path that the rat can follow to reach the destination.
The following is the binary representation of the path shown in the above diagram.
Only the entries marked using the number 0 represent the path.
Approach
The approach is to create a recursive method. The recursive method will follow a path starting from the source cell and will check whether the path reaches the destination cell or not. If the path is not successful in reaching the destination cell, then backtrack and try out the other paths.
Algorithm
On the basis of the above approach, the following algorithm is written.
- Create a result matrix (result[R][C]), and fill each cell of the matrix with 1’s.
- Create a recursive method that takes the initial matrix, the result matrix, and the current position of the rat (which is (0, 0) initially).
- If the position goes out of the matrix or the rat lands in the position is not valid, then return. It is because that path cannot be the correct path. Therefore, no need to proceed further.
- Put the value of the cell result[r][c] as 0 and then check whether the current cell is the destination cell or not. If the destination cell is reached, display the result matrix and terminate.
- If the destination cell is not reached, then recursively check for the position (r + 1, c) and (r, c + 1).
- If the rat cannot reach the destination cell form the position (r, c), then unmark the position or cell (r, c), that is, result[r][c] = 1.
Implementation
Let’s see how one can implement the above mathematical formula. Observe the following example.
FileName: RatMazeProblem.java
Output:
The resultant matrix is: 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 0
Time Complexity: The recursion, mentioned in the above example, can run upper-bound 2^(n^2) times. Therefore, the time complexity of the above program is O(2 ^ (n ^ 2)).
Space Complexity: Since we have used an extra matrix (maz[][]). Therefore, the space complexity of the above program is O(n ^ 2).