Rat In A Maze
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/
* Problem: Rat In A Maze
* Group: 07. Recursion
*/
/
* ============================================================================================
* PROBLEM: Rat In a Maze
* ============================================================================================
*
* ---------------------
* 1. Problem Description
* ---------------------
* Given a square grid A of size N x N.
* - '1' represents a traversable cell.
* - '0' represents a blocked cell.
*
* The Rat starts at (0, 0) and wants to reach the destination (N-1, N-1).
* Movement allowed: Only RIGHT or DOWN.
*
* Task:
* Return a grid of the same size N x N that marks the path taken.
* - The cells part of the successful path should be '1'.
* - All other cells (including traversable ones not in the path) should be '0'.
*
* ---------------------
* 2. Logical Breakdown & Mathematical Formulation
* ---------------------
* Let A[N][N] be the input grid.
* Let Sol[N][N] be the solution grid, initially all 0.
*
* We define a recursive function Solve(r, c):
*
* Validity Check:
* A cell (r, c) is valid if:
* 1. It is within bounds (0 <= r < N, 0 <= c < N).
* 2. It is traversable (A[r][c] == 1).
*
* Recursion Steps (Backtracking):
* 1. Mark Sol[r][c] = 1 (Assume this cell is part of the path).
*
* 2. Base Case:
* If (r == N-1) AND (c == N-1), we have reached the destination. Return True.
*
* 3. Recursive Calls (Greedy approach usually tries moves in specific order):
* - Try Move Right: If Solve(r, c + 1) returns True -> Return True (Path found).
* - Try Move Down: If Solve(r + 1, c) returns True -> Return True (Path found).
*
* 4. Backtracking:
* If neither Right nor Down leads to a solution, it means (r, c) is part of a dead end.
* - Unmark Sol[r][c] = 0.
* - Return False.
*
* ---------------------
* 3. Constraints & Complexity Analysis
* ---------------------
* Constraints:
* 1 <= N <= 4 (Extremely small).
*
* Time Complexity:
* O(2^(N^2)) in general backtracking, but with only Right/Down moves, the path length is 2N-2.
* The complexity is closer to O(2^(2N)).
* For N=4, this is negligible.
*
* Space Complexity:
* O(NN) for the solution grid and O(N) for recursion stack depth.
*
* ---------------------
* 4. Input / Output Format
* ---------------------
* Input:
* - A 2D integer array A.
*
* Output:
* - A 2D integer array representing the path.
*
* ---------------------
* 5. Examples
* ---------------------
* Input 1:
* [ [1, 0],
* [1, 1] ]
* Path: (0,0) -> Down is blocked(0) -> Right is blocked? No wait.
* (0,0) is 1. (0,1) is 0 (Blocked).
* Only move is Down to (1,0). From (1,0) Move Right to (1,1).
* Output 1:
* [ [1, 0],
* [1, 1] ]
* Note: Path is (0,0)->(1,0)->(1,1).
*
* Input 2:
* [ [1, 1, 1],
* [1, 0, 1],
* [0, 0, 1] ]
* Path: (0,0)->(0,1)->(0,2)->(1,2)->(2,2).
* Output 2:
* [ [1, 1, 1],
* [0, 0, 1],
* [0, 0, 1] ]
* Note: Input (1,0) was 1, but it's not in the solution path, so output (1,0) is 0.
*
* ============================================================================================
/
public class RatInAMaze {
public ArrayList