AlgoViz
HomeBacktracking

Rat in a Maze

Hard

Try each direction, unmark on the way back

Problem

A rat starts at the top-left of a grid (1=open, 0=blocked) and must reach the bottom-right. Return all paths as strings of moves (D,L,R,U).

In simple words

Move in all four directions, marking the current cell blocked so you don't revisit, and backtrack.

The idea

From each cell try the four moves in a fixed order, recursing into any that is open and unvisited, and record the letter for that move. Unmarking the cell as the recursion returns is what lets a later path reuse it — without that you would find only one route.

The trick

  • Fix the direction order (D, L, R, U) and the paths come out lexicographically sorted.
  • Mark visited before recursing, unmark after — the defining move of backtracking.
  • A path is complete when you reach the destination cell.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
0
0
1

Step 1 of 2. Here's the example — [[1,0],[1,1]] Values: 1, 0.

1/2
Optimal
timeO(4^(m*n))spaceO(m*n)
1dfs(r,c,path):2  if at end: output path; return3  for each move (D,L,R,U) that is open and unvisited:4    mark; dfs(nr,nc,path+move); unmark

Input

array
[1, 0]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

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:
Paths from top-left to bottom-right using D/L/R/U.

Example 2

Input:
maze = [[1,0],[1,1]]
Output:
['DR']
Explanation:
Only DR reaches the exit.

Example 3

Input:
maze = [[1,1],[0,1]]
Output:
['RD']
Explanation:
Go right then down → RD.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.