Rat in a Maze
Find any path from the top-left to the bottom-right of a grid through open cells, moving in any of 4 directions, never revisiting a cell. Classic 4-directional backtracking with a visited set.
- Category
- Backtracking
- Time complexity
- O(4^(n²))
- Space complexity
- O(n²)
Pseudocode
mark cell visited, extend path if at goal: done try all 4 directions none work ⇒ unmark, backtrack
Reference implementation
def solve(r, c):
if not valid(r, c) or visited[r][c]: return False
visited[r][c] = True; path.append((r, c))
if (r, c) == goal: return True
for dr, dc in DIRS:
if solve(r+dr, c+dc): return True
path.pop(); return False # backtrack