Topics › Recursion and Backtracking › Trying out all Combos / Hard

Rat in a Maze

Hard TUF ID 872 A2ZSDE

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

A rat sits in the top-left cell (0, 0) of an n x n maze and wants to reach the bottom-right cell (n-1, n-1). Each cell holds 1 (open) or 0 (blocked). In one move the rat goes to a side-adjacent open cell: D (down), L (left), R (right) or U (up). A cell may appear at most once in a path. Return every possible path as a string of moves, sorted in lexicographic order. If the source or the destination is blocked, or no path exists, return an empty list.

Constraints: 2 ≤ n ≤ 5 in the original statement, which keeps the exponential number of paths manageable.

Example 1

maze = 1 0 0 0
       1 1 0 1
       1 1 0 0
       0 1 1 1
answer = ["DDRDRR", "DRDDRR"]
// both paths go down the left side, cross at row 3, and finish along the bottom row

Example 2

maze = 1 0
       1 0
answer = []     // the destination (1, 1) is blocked

Approach 1: Brute force, DFS with a visited matrix

Intuition. Every path is a sequence of choices made cell by cell, so recursion generates them all: stand on a cell, pick a direction, move if the target is in bounds, open and not already on the current path, and continue. When the destination is reached, the accumulated move string is one answer. The “not already on the path” rule is essential, otherwise the rat walks in circles for ever; a visited matrix enforces it.

The order of the four branches is not arbitrary. Trying D, then L, then R, then U happens to be alphabetical ('D' < 'L' < 'R' < 'U'), and that is why the list comes out sorted with no extra sort (more on this below).

Algorithm.

1. If the source or destination is 0, return the empty list.
2. explore(r, c): if (r, c) is the destination, record the current string and return.
3. Mark (r, c) visited.
4. For D, L, R, U in that order: if the neighbour is inside the maze, open and unvisited, append the letter, recurse, and remove the letter afterwards.
5. Unmark (r, c) so other paths may pass through it.

static List<String> bruteForce(int[][] maze) {
    List<String> paths = new ArrayList<>();
    int n = maze.length;
    if (n == 0 || maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return paths;
    boolean[][] visited = new boolean[n][n];
    explore(0, 0, maze, n, new StringBuilder(), visited, paths);
    return paths;
}

private static void explore(int r, int c, int[][] maze, int n, StringBuilder path, boolean[][] visited, List<String> paths) {
    if (r == n - 1 && c == n - 1) {
        paths.add(path.toString());
        return;
    }
    visited[r][c] = true;
    if (r + 1 < n && !visited[r + 1][c] && maze[r + 1][c] == 1) {          // Down
        path.append('D');
        explore(r + 1, c, maze, n, path, visited, paths);
        path.deleteCharAt(path.length() - 1);
    }
    if (c - 1 >= 0 && !visited[r][c - 1] && maze[r][c - 1] == 1) {         // Left
        path.append('L');
        explore(r, c - 1, maze, n, path, visited, paths);
        path.deleteCharAt(path.length() - 1);
    }
    if (c + 1 < n && !visited[r][c + 1] && maze[r][c + 1] == 1) {          // Right
        path.append('R');
        explore(r, c + 1, maze, n, path, visited, paths);
        path.deleteCharAt(path.length() - 1);
    }
    if (r - 1 >= 0 && !visited[r - 1][c] && maze[r - 1][c] == 1) {         // Up
        path.append('U');
        explore(r - 1, c, maze, n, path, visited, paths);
        path.deleteCharAt(path.length() - 1);
    }
    visited[r][c] = false;
}

Complexity. Time O(4^(n²)) in the loosest bound: each of up to n² cells on a path offers at most four choices. In practice the no-revisit rule caps it at the number of simple paths in the grid, which is still exponential (a fully open 4 x 4 maze has 184 corner-to-corner paths; 5 x 5 has 8512). Space O(n²) for visited plus a recursion depth of at most n².

Why the result is sorted. Take two different paths and look at the first position where they differ. Both share the prefix before it, so both reach the same cell at that moment, and the DFS at that cell tries the smaller letter first. Hence the path with the smaller letter is recorded first. Lexicographic order on strings is defined by exactly that first differing character, so the recorded order is the sorted order. (No path is a proper prefix of another, because a proper prefix ends before the destination.)

Approach 2: Optimal, direction arrays and in-place marking

Intuition. The four nearly identical blocks above are a maintenance hazard: a typo in one of them is easy to miss. Put the row offsets, column offsets and letters into three parallel arrays and loop over them. Keeping the arrays in D, L, R, U order preserves the sorted output.

The visited matrix can also go. While a cell is on the current path, temporarily set it to 0; the normal “is the neighbour open?” test then rejects it. Restore the 1 when the recursion returns. The maze is back to its original state when the method finishes, which the test confirms with Arrays.deepEquals.

A fixed char[] buffer of size n·n replaces the StringBuilder: a simple path visits at most n² cells, so it makes at most n² - 1 moves. Passing the current length down instead of deleting characters makes the undo implicit.

Algorithm.

1. Same guards for the source and destination.
2. dfs(r, c, len): at the destination, add new String(buf, 0, len) and return.
3. Set maze[r][c] = 0.
4. For d = 0..3: compute the neighbour; if inside and == 1, write MOVE[d] at buf[len] and recurse with len + 1.
5. Set maze[r][c] = 1 again.

static List<String> optimal(int[][] maze) {
    List<String> paths = new ArrayList<>();
    int n = maze.length;
    if (n == 0 || maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return paths;
    dfs(0, 0, maze, n, new char[n * n], 0, paths);  // a simple path visits at most n*n cells, so n*n - 1 moves
    return paths;
}

private static void dfs(int r, int c, int[][] maze, int n, char[] buf, int len, List<String> paths) {
    if (r == n - 1 && c == n - 1) {
        paths.add(new String(buf, 0, len));
        return;
    }
    maze[r][c] = 0;                                  // block the cell while it is on the current path
    for (int d = 0; d < 4; d++) {
        int nr = r + DR[d], nc = c + DC[d];
        if (nr >= 0 && nr < n && nc >= 0 && nc < n && maze[nr][nc] == 1) {
            buf[len] = MOVE[d];
            dfs(nr, nc, maze, n, buf, len + 1, paths);
        }
    }
    maze[r][c] = 1;                                  // restore it for the other branches
}

with DR = {1, 0, 0, -1}, DC = {0, -1, 1, 0} and MOVE = {'D', 'L', 'R', 'U'}.

Dry run on Example 1. Cells are (row, col); the buffer is shown as a string.

The recursion then unwinds without further hits: ["DDRDRR", "DRDDRR"].

Complexity. Same exponential time as Approach 1; the asymptotic class cannot improve because the output itself can be exponential. Space drops to the n² buffer and the recursion stack; no visited matrix.

Edge cases and pitfalls

• Blocked source or destination. Return [] immediately. Some judges (GFG) print -1 in this case; adapt the return value to the platform, the search is the same.
• n = 1 with an open cell. The rat is already at the destination; the single valid path is the empty string. Both methods return [""].
• Missing the undo. Forgetting visited[r][c] = false (or maze[r][c] = 1) makes later paths unable to cross cells used by earlier ones, silently dropping answers. In Example 1 the cell (2,1) is on both paths.
• Marking the destination. The code records the path and returns before marking, so no restore is needed there. If you mark first, restore before returning.
• Direction order. Any order gives the same set of paths, but only D, L, R, U (alphabetical) gives them sorted for free. With another order, sort the list at the end.
• Buffer size. 2n moves is not enough: paths may wander. n·n is the safe bound for a simple path.
• Unreachable open regions. Open cells that no path can reach (the centre of the ring maze in the tests) are simply never visited.

Related problems

• Word Search is the same grid DFS, but matching letters and stopping at the first success.
• Number of islands uses the same direction arrays without the need to undo marks.
• Grid unique paths counts right/down paths only, where overlapping subproblems make DP possible.
• N Queen collects all solutions of a different constraint problem with the same backtracking template.