GeeksforGeeks Medium

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.

backtrackingmatrix

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.

How to spot this pattern

Grid backtracking: mark the cell on entry so the path can't revisit itself, explore each direction, then unmark on the way out so other paths may use the cell. The unmark is what separates path enumeration from flood fill — a flood marks permanently because it only needs to visit once.

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

▶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

Common pitfalls

Not restoring the cell after exploring

✗ Wrong

maze[r][c] = 0
for ch, dr, dc in moves:
    ...

✓ Right

maze[r][c] = 0
for ...:
    ...
maze[r][c] = 1                # unmark

Cells stay blocked for every subsequent path, so only the first route is ever found. The mark exists to prevent revisiting within one path — once that path unwinds, the cell is available again.

Trying directions in an arbitrary order

✗ Wrong

moves = [("U",-1,0),("R",0,1),("D",1,0),("L",0,-1)]

✓ Right

moves = [("D",1,0),("L",0,-1),("R",0,1),("U",-1,0)]

GFG requires the paths in lexicographic order, and exploring in D-L-R-U order produces them sorted without a final sort. Any other order gives the same set of paths in the wrong sequence.

Not checking that the start or end is open

✗ Wrong

go(0, 0)
return res

✓ Right

if not maze[0][0] or not maze[n-1][n-1]: return res

A blocked start would still be marked and explored from, and a blocked destination makes every search futile. Both guards are cheap and stop the recursion before it begins.

06

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.

07

Complexity

Time

O(4^(n²))

Space

O(n²)

Worst-case exponential; pruning makes real mazes fast.