1. One-Liner
Rat in a Maze explores moves from start to goal on a grid, retreating when a path hits a wall or a dead end.
2. The Problem It Solves
A binary maze (1 = open, 0 = blocked) has a rat at top-left and cheese at bottom-right (common variant). Determine whether a path exists (and sometimes list one path) using only valid moves—often up/down/left/right without revisiting cells in the same attempt.
3. The Core Idea
DFS: from current cell, try each neighbor in order; mark visited to avoid cycles; if a neighbor reaches the goal, succeed; if all fail, unmark (backtrack) so other branches can use this cell. This is backtracking on an implicit grid graph.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Bounds | Reject out-of-grid indices |
| 2. Obstacle | Skip 0 cells |
| 3. Visited | Skip already visited in this path |
| 4. Goal | If (n-1,m-1), return success |
| 5. Recurse | Mark current, try 4 directions |
| 6. Backtrack | Unmark when returning failure |
5. Dry Run Example
3×3 all ones: go right twice, down twice works. If one cell blocked in the corner, DFS tries alternatives or returns false—shows exploration order matters for “first path found.”
6. Key Properties
| Property | Value |
|---|---|
| Graph model | Cells = vertices, edges = legal moves |
| Cycle handling | visited array or mark/unmark |
| BFS option | Shortest path in unweighted grid |
7. Where It Is Used
| Domain | Use |
|---|---|
| Robotics / games | Simple grid navigation |
| Interviews | Warm-up for flood fill and path problems |
| Mazes | Count all paths variant with DP sometimes |
8. Interview Tips
State time vs space for DFS vs BFS; clarify diagonal moves and revisit rules; for “count paths,” often DP after memoizing coordinates.
9. Comparison with Other Approaches
| Approach | When |
|---|---|
| DFS + backtrack | Existential path, reconstruct one path |
| BFS | Shortest steps in unweighted grid |
| Dijkstra / A* | Weighted grids |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(4^{R·C}) worst without memo for exhaustive; O(R·C) per DFS visit marking |
| Space | O(R·C) visited + recursion stack |
Implementation Example (PYTHON)
def rat_reaches_goal(maze: list[list[int]]) -> bool:
if not maze or maze[0][0] == 0:
return False
n, m = len(maze), len(maze[0])
vis = [[False] * m for _ in range(n)]
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
def dfs(r: int, c: int) -> bool:
if r == n - 1 and c == m - 1:
return True
vis[r][c] = True
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m:
if maze[nr][nc] == 1 and not vis[nr][nc]:
if dfs(nr, nc):
return True
vis[r][c] = False
return False
return dfs(0, 0)