Rat in a Maze
In an n×n grid of 0/1 cells, find all paths from (0,0) to (n−1,n−1) moving U/D/L/R through 1-cells, no cell reused.
Open on GeeksforGeeks ↗02
Intuition
Classic backtracking on a grid: at each cell try the four moves (in lexicographic order D,L,R,U so paths come out sorted), mark the cell visited so the path can't loop, and unmark when retreating.
03
Approach
1
Try moves in D, L, R, U order
Emitting choices in alphabetical order yields the required sorted path strings for free.
2
Mark, recurse, unmark
Set visited before recursing, clear after — the grid doubles as the visited set.
3
Prune invalid moves
Out of bounds, walls (0), and visited cells are rejected before recursion, keeping the tree tight.
04
Solution & live demo
python
▶1def find_paths(maze):
▶2 n = len(maze)
▶3 res, path = [], []
▶4 if not maze[0][0] or not maze[n-1][n-1]: return res
▶5 moves = [("D",1,0),("L",0,-1),("R",0,1),("U",-1,0)]
▶6 def go(r, c):
▶7 if (r, c) == (n-1, n-1):
▶8 res.append("".join(path)); return
▶9 maze[r][c] = 0 # mark visited
▶10 for ch, dr, dc in moves:
▶11 nr, nc = r + dr, c + dc
▶12 if 0 <= nr < n and 0 <= nc < n and maze[nr][nc]:
▶13 path.append(ch)
▶14 go(nr, nc)
▶15 path.pop()
▶16 maze[r][c] = 1 # unmark
▶17 go(0, 0)
▶18 return res
05
Edge cases
Start or end cell is 0
No path exists; return empty list.
1×1 grid of 1
Start is the destination — one path, the empty string.
06
Complexity
Time
O(4^(n²))
Space
O(n²)
Worst-case exponential; pruning makes real mazes fast.