Problem statement
Find every path from (0,0) to (n−1,n−1) in a square binary maze. A 1 is open and a 0 is blocked. Move one square Down, Left, Right or Up, but never visit a cell twice within one path.
Return direction strings in lexicographic order; return an empty list if no route exists. GFG Rat in a Maze permits 2≤n≤5. This is not a shortest-path question and does not allow jumps or diagonal moves.
The teaching method leaves the supplied maze unchanged. It additionally handles an empty maze and a 1×1 maze as defensive extensions outside those published bounds.
Constraints & requirements
- CONTRACT
- GFG: 2≤n≤5; 1=open, 0=blocked. A cell cannot repeat within a path. Return [] when no route exists and preserve the maze. The helper also handles an empty maze and a 1×1 maze defensively.
Examples 3 test cases
Example 1 Case 1
- Input
[[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]- Output
["DDRDRR","DRDDRR"]
Both routes reach (3,3) through open cells without repeating a cell.
Example 2 Case 2
- Input
[[1,1],[1,1]]- Output
["DR","RD"]
Down-first and right-first are different valid routes.
Example 3 Case 3
- Input
[[0,1],[1,1]]- Output
[]
The start is blocked; there is no legal first visit.
Hints Optional
01Hint 1
Mark cells used by the current route, not cells discovered permanently.
02Hint 2
Try D,L,R,U in that order for sorted path strings.
03Hint 3
Save a direction-string copy at the destination and restore both the path and visited cell after every child.
How to think before coding
Visited means reserved by THIS route, not permanently explored. Mark the current cell, try valid D/L/R/U neighbors, and unmark before returning to the caller. Save a path snapshot at the destination. Restore both the cell mark and the appended direction after a child so another route can reuse the cell without repeating it inside one route.
Brute force and the improvement
A finite brute-force baseline enumerates all direction strings of lengths up to V−1, where V=n² cells, then validates boundaries, open cells, nonrepetition and arrival at the destination. Every simple route has at most V−1 moves. A loose O(V·4^V) validation bound and O(V) working space show why this is wasteful. A walk with no visited rule is NOT a valid baseline: it can loop forever. Backtracking validates each move immediately and abandons impossible prefixes, while still enumerating all requested routes.
Intuition: visited means part of this route
If we walk down and immediately walk up, we return to the same cell. Without a visited check, recursion can loop or generate routes with repeated cells.
However, a permanent visited mark is also wrong. A cell used in one completed route may belong to a different valid route. Mark it while exploring the current branch, then release it when returning to try a sibling.
Two objects describe different things: visited says which cells are reserved; path records the letters of the route. Both must be restored together. The maze itself describes walls, not temporary reservations.
Algorithm
- Reject a blocked start or blocked destination before searching.
- Mark the start visited and begin with an empty direction list.
- At the destination, join the direction list into a saved String and return.
- Try D,L,R,U in that order.
- For each in-bounds open unvisited destination, mark it, append the move and recurse.
- After the child returns, remove the move and unmark that destination.
D,L,R,U is alphabetical order. The depth-first search therefore produces sorted strings without a final sort. No valid route is a prefix of another here: a route stops as soon as it reaches the destination.
Java solution
The maze itself determines n. Blocked endpoints return no paths, and each invocation has a fresh result list. The search preserves the input maze.
import java.util.*;
class Solution {
private static final int[] MAZE_DR = {1, 0, 0, -1}, MAZE_DC = {0, -1, 1, 0};
private static final String[] MAZE_STEP = {"D", "L", "R", "U"}; // Alphabetical traversal order.
public static List<String> ratInMaze(int[][] maze) {
List<String> result = new ArrayList<>(); // Repeated calls must not retain earlier paths.
int n = maze.length; // Derive dimensions from the actual square maze, not a separate prompt.
if (n == 0 || maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return result; // Defensive empty/blocked endpoints.
boolean[][] visited = new boolean[n][n];
visited[0][0] = true; // The start is already on the active path.
mazePaths(maze, visited, 0, 0, new ArrayList<>(), result);
return result; // DFS in D,L,R,U order emits paths lexicographically.
}
private static void mazePaths(int[][] maze, boolean[][] visited, int row, int col,
List<String> path, List<String> result) {
int n = maze.length;
if (row == n - 1 && col == n - 1) {
result.add(String.join("", path)); // Save direction text, not mutable path references.
return; // A route ends at the destination; do not explore past it.
}
for (int move = 0; move < 4; move++) {
int nr = row + MAZE_DR[move], nc = col + MAZE_DC[move];
if (nr < 0 || nr >= n || nc < 0 || nc >= n || maze[nr][nc] == 0 || visited[nr][nc]) continue;
visited[nr][nc] = true; path.add(MAZE_STEP[move]); // Reserve the cell and its incoming move.
mazePaths(maze, visited, nr, nc, path, result); // Enumerate every continuation.
path.remove(path.size() - 1); visited[nr][nc] = false; // Release only this branch's choice.
}
}
public static void main(String[] args) {
int[][] maze = {{1,0,0,0},{1,1,0,1},{1,1,0,0},{0,1,1,1}};
System.out.println(ratInMaze(maze)); // [DDRDRR, DRDDRR]
}
}The invocation prints [DDRDRR, DRDDRR]. Saving the joined String keeps each answer independent of subsequent changes to path.
Recursion tree and dry run

Read the text transcript
Follow the Java, step by step
Example: maze = [[1,1],[1,1]]
What to track: This complete 2×2 example uses the same D,L,R,U order as Java. path holds direction strings; visited reserves cells for the current route only.
-
Reserve the starting cell
Java operationvisited[0][0] = true;Stateat (0,0); path = []; visited contains (0,0)The root may not return to the start within one route.
-
Go down
Java operationvisited[nr][nc] = true; path.add(MAZE_STEP[move]);Statemove = D; child at (1,0); path = [D]; visited adds (1,0)The child tries D and L first, but both are out of bounds. R is the next legal choice.
-
Go right and save the route
Java operationresult.add(String.join("", path));Stateat destination (1,1); path = [D,R]; result = ["DR"]The destination base case saves text and returns without exploring past the finish.
-
Undo the child’s incoming move
Java operationpath.remove(path.size() - 1); visited[nr][nc] = false;Stateback at (1,0); path = [D]; (1,1) released; U points to the already reserved startThat U branch is rejected. The root later removes D and releases (1,0) after its entire subtree finishes.
-
Explore the root’s right branch
Java operationmazePaths(maze, visited, nr, nc, path, result);Stateroot path restored to []; R enters (0,1); its D child reaches (1,1) with path = [R,D]The destination is available again because the previous route released it. This second route saves "RD".
-
Restore and finish
Java operationpath.remove(path.size() - 1); visited[nr][nc] = false;Stateresult = ["DR","RD"]; path = []; only (0,0) remains marked in the private visited arrayMarks are branch-local reservations, not permanent global discovery. Keeping them globally would incorrectly suppress the second route.
Final result: ["DR","RD"]; all non-start visited marks are restored and the maze is unchanged.
maze:
1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1
(0,0), path ""
└─ D → (1,0)
├─ D → (2,0)
│ └─ R → (2,1) → D → (3,1) → R → (3,2) → R → (3,3)
│ save DDRDRR; unwind and undo this route
└─ R → (1,1)
└─ D → (2,1) → D → (3,1) → R → (3,2) → R → (3,3)
save DRDDRRThis excerpt shows the successful branches, omitting rejected moves and dead ends. For DDRDRR, the visited cells are (0,0),(1,0),(2,0),(2,1),(3,1),(3,2),(3,3). The later route may use (2,1) again because that earlier branch has returned and released it.
After reaching (3,3), its waiting caller removes the last R and clears that child’s cell. Each higher caller similarly undoes only the choice it made. The start stays reserved for the whole search so no branch can revisit it.
For a defensive 1×1 open maze, the destination is already reached. The answer is a list containing the empty string "": one zero-move route, not an empty list. Java’s list display can make that distinction hard to see; inspect its size or use quoted output.
Why it works
The active path consists only of open orthogonally connected cells with no repeated cell. Each safe child preserves that invariant. Reaching the destination therefore describes a valid route.
Every legal next direction is tried, so every simple route has a matching branch. Undo restores reservations before another branch, preventing one route from hiding another. A direction string uniquely describes its route from the fixed starting square, so no duplicate route is saved.
Complexity and alternative approaches
Let B=n² cells, V the number of visited search states and S the total characters in saved routes. Time is O(V+S): each state tries four moves, and each successful route is copied once.
A loose search bound is O(4^B), because a simple path cannot use more than B cells. Saved paths can be exponentially numerous; copying a route costs up to O(B). A safe combined bound is O(B·4^B), rather than treating saved direction strings as free.
Visited, path and recursive stack use O(B) auxiliary space, excluding the output. Mutating maze cells temporarily can replace the visited matrix, but requires guaranteed restoration. A separate matrix is clearer and preserves the caller’s grid throughout.
BFS is useful for the shortest route or distance, not a replacement for enumerating every simple path. A right/down-only DP counts a different movement contract and cannot be substituted for four-direction enumeration.
Common mistakes
- Starting from a blocked cell because only neighbors were checked.
- Keeping a global visited set after returning from a branch.
- Forgetting to undo either the direction or the reserved cell.
- Stopping after the first destination when all routes are requested.
- Reporting output space as O(n²) despite exponentially many saved routes.