05. Rat in a Maze
✅ GFG solution to the Rat in a Maze problem: find all possible paths from source to destination using backtracking and DFS technique. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
Consider a rat placed at position (0, 0) in an n x n square matrix maze[][]. 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.
Your task is to find all possible paths the rat can take to reach the destination, starting from (0, 0) and ending at (n-1, n-1), under the condition that the rat cannot revisit any cell along the same path. The rat can only move to adjacent cells that are within the bounds of the matrix and not blocked.
If no path exists, return an empty list.
Note: Return the final result vector in lexicographically smallest order.
📘 Examples
Example 1
Input: maze[][] = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]
Output: ["DDRDRR", "DRDDRR"]
Explanation: The rat can reach the destination at (3, 3) from (0, 0) by two paths -
DRDDRR and DDRDRR, when printed in sorted order we get DDRDRR DRDDRR.Example 2
Example 3
🔒 Constraints
$2 \le n \le 5$
$0 \le \text{maze}[i][j] \le 1$
✅ My Approach
The optimal approach uses Backtracking with DFS (Depth-First Search) to explore all possible paths from source to destination:
Backtracking + DFS
Initial Check:
Verify if the starting cell
(0, 0)and destination cell(n-1, n-1)are both open (value = 1).If either is blocked, return an empty result immediately.
Mark as Visited:
Before exploring from a cell, mark it as visited by setting
maze[i][j] = 0.This prevents the rat from revisiting the same cell in the current path.
Explore Four Directions:
Try all four directions in lexicographical order: D (Down), L (Left), R (Right), U (Up).
For each direction, check if the next cell is valid (within bounds and not blocked).
Recursively explore the next cell by appending the direction character to the current path.
Base Case - Destination Reached:
When the rat reaches
(n-1, n-1), add the current path string to the result list.
Backtrack:
After exploring all paths from the current cell, restore it by setting
maze[i][j] = 1.This allows the cell to be used in other potential paths.
Return All Paths:
The result naturally maintains lexicographical order due to the direction exploration sequence.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(4^(n²)), as in the worst case, we explore all four directions from each cell. The total number of cells is n², and at each cell, we have up to 4 choices, leading to an exponential time complexity.
Expected Auxiliary Space Complexity: O(n²), where the recursion stack can go as deep as n² in the worst case (visiting all cells), and we modify the maze in-place for marking visited cells.
🧑💻 Code (C++)
⚡ View Alternative Approaches with Code and Analysis
📊 2️⃣ Visited Array Approach
💡 Algorithm Steps:
Use a separate boolean visited array instead of modifying the maze.
Mark cells as visited during exploration to avoid cycles.
Recursively explore all four directions in lexicographical order.
Backtrack by unmarking visited cells after exploring all paths.
📝 Complexity Analysis:
Time: ⏱️ O(4^(n²)) - At each cell, we have 4 choices (worst case)
Auxiliary Space: 💾 O(n²) - Extra visited matrix and recursion stack
✅ Why This Approach?
Preserves original maze input without modification
Clear separation of concerns with dedicated visited tracking
Easier to debug and understand state changes
📊 3️⃣ Direction Array with Loop
💡 Algorithm Steps:
Define direction vectors and corresponding characters in arrays.
Use a single loop to iterate through all four directions.
Check validity and recursively explore each valid direction.
Automatically maintains lexicographical order with proper array ordering.
📝 Complexity Analysis:
Time: ⏱️ O(4^(n²)) - Exploring all possible paths
Auxiliary Space: 💾 O(n²) - Recursion stack depth
✅ Why This Approach?
Compact and maintainable with direction arrays
Easy to modify directions or add new ones
Cleaner code structure with loop-based exploration
📊 4️⃣ Bitmasking Visited State
💡 Algorithm Steps:
Use bitmasking to represent visited cells efficiently.
Each cell position is mapped to a bit in an integer.
Set bit when visiting, unset during backtracking.
Memory efficient for smaller maze sizes (up to 5x5).
📝 Complexity Analysis:
Time: ⏱️ O(4^(n²)) - Same path exploration complexity
Auxiliary Space: 💾 O(n²) - Recursion stack only (O(1) extra for bitmask)
✅ Why This Approach?
Space-efficient visited state representation
No need for separate visited array
Excellent for competitive programming with size constraints
🆚 🔍 Comparison of Approaches
🚀 Approach
⏱️ Time Complexity
💾 Space Complexity
✅ Pros
⚠️ Cons
🏷️ In-place Modification
🟢 O(4^(n²))
🟢 O(n²)
🚀 Minimal extra space
🔧 Modifies input maze
🔍 Visited Array
🟢 O(4^(n²))
🟡 O(n²)
📖 Preserves original maze
💾 Extra array overhead
📊 Direction Array
🟢 O(4^(n²))
🟢 O(n²)
🎯 Clean maintainable code
🔧 Slightly more initialization
🔄 Bitmasking
🟢 O(4^(n²))
🟢 O(n²)
⭐ Space efficient tracking
🐌 Limited to smaller mazes
🏆 Best Choice Recommendation
🎯 Scenario
🎖️ Recommended Approach
🔥 Performance Rating
🏅 Optimal space usage
🥇 In-place Modification
★★★★★
📖 Input preservation needed
🥈 Visited Array
★★★★☆
🔧 Scalability & Maintenance
🥉 Direction Array
★★★★☆
🎯 Competitive Programming
🏅 Bitmasking
★★★★☆
☕ Code (Java)
🐍 Code (Python)
🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated