Lesson

13.11Rat in a Maze

Problem Statement

Consider a rat placed at position (0, 0) in an n x n square matrix mat. The rat's goal is to reach the destination at position (n-1, n-1). The rat can move in four possible directions:

'U' (Up)
'D' (Down)
'L' (Left)
'R' (Right)

The matrix contains only two possible values:

0: A blocked cell through which the rat cannot travel.
1: A free cell that the rat can pass through.

Note:

In a path, no cell can be visited more than once.
If the source cell (0, 0) is 0, the rat cannot move to any other cell.
In case of no path, return an empty list.

Example Inputs

Example 1:

Example 2:

Example 3:

Problem Solution

Approach

To find all possible paths the rat can take to reach the destination, we can use a recursive backtracking approach. The idea is to explore all possible moves (Up, Down, Left, Right) from the current cell, ensuring that:

The move stays within the bounds of the matrix.
The cell is not blocked (0).
The cell has not been visited in the current path to avoid cycles.

By systematically exploring each direction and backtracking when a path is blocked or when the destination is reached, we can generate all valid paths from the source to the destination.

Steps

Initial Check:
- If the source cell (0, 0) is blocked (0), return an empty list as no path exists.
Sort Paths (Optional):
- To ensure that the output paths are in lexicographical order, you can sort the final list of paths before returning.
Recursive Backtracking Function (backtrack):
- Parameters:
  - i: Current row index.
  - j: Current column index.
  - path: String representing the path taken so far.
  - matrix: The maze matrix.
  - n: Size of the matrix.
  - ans: Array to store all valid paths.
- Base Case:
  - If the current position (i, j) is the destination (n-1, n-1), add the path to ans.
- Mark the Current Cell as Visited:
  - To avoid revisiting the same cell, mark the current cell as blocked by setting matrix[i][j] = 0.
- Explore All Four Directions:
  - Up ('U'): Move to (i-1, j) if within bounds and not blocked.
  - Down ('D'): Move to (i+1, j) if within bounds and not blocked.
  - Left ('L'): Move to (i, j-1) if within bounds and not blocked.
  - Right ('R'): Move to (i, j+1) if within bounds and not blocked.
- Backtrack:
  - After exploring all possible moves from the current cell, unmark the cell by setting matrix[i][j] = 1 to allow its use in other paths.
Initiate Backtracking:
- Start the recursion from the source cell (0, 0) with an empty path.
Return the Result:
- After exploring all paths, return the ans array containing all valid paths.

Time & Space Complexity

Time Complexity: O(4^(n^2))
- In the worst case, where all cells are free (1), the rat can explore all possible directions at each cell, leading to an exponential number of paths.
Space Complexity: O(n^2)
- The recursion stack can go as deep as the number of cells in the matrix, and each path can take up to n^2 space in the worst case.

Code Snippet

Dry Run

Let's perform a dry run with the following input:

Goal: Find all paths from (0, 0) to (2, 2).

Steps:

Initial Call: backtrack(0, 0, "")
- Current Position: (0, 0)
- Path: ""
- Mark (0, 0) as visited.
Explore Directions from (0, 0)
- Down ('D'): Move to (1, 0)
  - Path: "D"
  - Mark (1, 0) as visited.
- Backtrack from (1, 0)
  - Down ('D'): Move to (2, 0)
    - Path: "DD"
    - Mark (2, 0) as visited.
  - Backtrack from (2, 0)
    - Down ('D'): Move to (3, 0) → Out of bounds. Skip.
    - Left ('L'): Move to (2, -1) → Out of bounds. Skip.
    - Right ('R'): Move to (2, 1)
      - Path: "DDR"
      - Mark (2, 1) as visited.
    - Backtrack from (2, 1)
      - Down ('D'): Move to (3, 1) → Out of bounds. Skip.
      - Left ('L'): Move to (2, 0) → Already visited. Skip.
      - Right ('R'): Move to (2, 2) → Destination reached.
        
        Path: "DDRR"
        
        Add "DDRR" to ans.
      - Up ('U'): Move to (1, 1) → Blocked (0). Skip.
    - Backtrack: Unmark (2, 1) and (2, 0).
  - Up ('U'): Move to (1, 0) → Already visited. Skip.
  - Left ('L'): Move to (1, -1) → Out of bounds. Skip.
  - Right ('R'): Move to (1, 1) → Blocked (0). Skip.
  - Backtrack: Unmark (1, 0).
- Left ('L'): Move to (0, -1) → Out of bounds. Skip.
- Right ('R'): Move to (0, 1)
  - Path: "R"
  - Mark (0, 1) as visited.
- Backtrack from (0, 1)
  - Down ('D'): Move to (1, 1) → Blocked (0). Skip.
  - Left ('L'): Move to (0, 0) → Already visited. Skip.
  - Right ('R'): Move to (0, 2)
    - Path: "RR"
    - Mark (0, 2) as visited.
  - Backtrack from (0, 2)
    - Down ('D'): Move to (1, 2)
      - Path: "RRD"
      - Mark (1, 2) as visited.
    - Backtrack from (1, 2)
      - Down ('D'): Move to (2, 2) → Destination reached.
        
        Path: "RRDD"
        
        Add "RRDD" to ans.
      - Left ('L'): Move to (1, 1) → Blocked (0). Skip.
      - Right ('R'): Move to (1, 3) → Out of bounds. Skip.
      - Up ('U'): Move to (0, 2) → Already visited. Skip.
    - Backtrack: Unmark (1, 2) and (0, 2).
  - Up ('U'): Move to (-1, 2) → Out of bounds. Skip.
  - Backtrack: Unmark (0, 2) and (0, 1).
- Backtrack: Unmark (0, 1) and (0, 0).
Final Paths in ans: ["DDRR", "RRDD"]

Complexity Analysis

Time Complexity: O(4^(n^2))
- In the worst case, where all cells are free (1), the rat can explore all possible directions at each cell, leading to an exponential number of paths.
Space Complexity: O(n^2)
- The recursion stack can go as deep as the number of cells in the matrix, and each path can take up to n^2 space in the worst case.

Optimizations:

Pruning Invalid Paths: By checking the validity of each move (within bounds, not blocked, not visited), we avoid unnecessary recursive calls.
Sorting Paths (Optional): Sorting the final list of paths ensures that the output is in lexicographical order, which can be useful for certain applications.

Conclusion

The Rat in a Maze problem is a classic example of using recursive backtracking to explore all possible paths from a source to a destination within a grid, considering constraints such as blocked cells and avoiding revisiting the same cell in a single path. By systematically exploring each possible move (Up, Down, Left, Right) and backtracking when a path is blocked or when the destination is reached, we can efficiently generate all valid paths.

Understanding this approach not only helps in solving similar pathfinding problems but also reinforces fundamental concepts in recursion, backtracking, and algorithm optimization. Implementing the solution in a functional style without using classes makes the code more concise and easier to understand, especially for beginners. By carefully managing the state and making strategic choices at each step, complex maze navigation problems become manageable and solvable with clarity and confidence.

Previous Next