Graph · 6 of 43
Search in a Maze
A mouse at the top left corner of a maze lists every way to reach the cheese at the bottom right, never stepping on the same square twice.
- Simple way
- time O(3^(N^2) + P * N^2 * log P)
room O(N^2) - Clever way
- time O(3^(N^2))
room O(N^2)
The problem, simply
You get an N by N maze. A 1 is an open square and a 0 is a wall. A mouse starts at the top left square and the cheese is at the bottom right. The mouse moves one square at a time: Down, Left, Right or Up. It may not step on a wall, leave the maze, or step on a square it already used on this trip.
Give back every possible trip as a string of letters like "DRDDRR", sorted in dictionary order. If there is no trip, give back an empty list. (A popular variant asks only for the shortest trip; it is covered below as a third way.)
A story to remember it
Picture it
The maze. S is the start, G is the cheese, X marks a wall. There are two trips: DDRDRR and DRDDRR.
- looking now
- answer
- ignored
Examples
Two trips
- In
[[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]- Out
[DDRDRR, DRDDRR]
Both trips meet at row 2, column 1. One gets there down the left wall first, the other cuts right first.
Wide open
- In
3 by 3, all 1- Out
12 trips, from DDRR to RRDLLDRR
With no walls there are many trips, including wiggly ones like RDLDRR. The number grows very fast with N.
Cheese behind a wall
- In
[[1,0],[1,0]]- Out
[]
The cheese square itself is a wall. Check both corners first and return an empty list.
Start on the cheese
- In
[[1]]- Out
one empty trip
The mouse is already there. The only trip has no moves.
Way 1: the simple way
Try every trip in any direction order, keep a separate "seen" board, and sort the answers at the end.
- If the start or the cheese is a wall, return nothing.
- Mark the current square as seen. Try Up, Down, Left, Right. Step into any open square that is not seen, and add its letter to the trip.
- On reaching the cheese, save the trip.
- Coming back, remove the last letter and unmark the square.
- Sort the saved trips.
class MazeAnyOrder {
static final int[] DR = {-1, 1, 0, 0};
static final int[] DC = {0, 0, -1, 1};
static final char[] NAME = {'U', 'D', 'L', 'R'};
public static List<String> findPaths(int[][] maze) {
int n = maze.length;
List<String> paths = new ArrayList<>();
if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return paths;
go(maze, 0, 0, new boolean[n][n], new StringBuilder(), paths);
Collections.sort(paths); // the judge wants sorted order
return paths;
}
static void go(int[][] maze, int r, int c, boolean[][] seen, StringBuilder path, List<String> paths) {
int n = maze.length;
if (r == n - 1 && c == n - 1) { paths.add(path.toString()); return; }
seen[r][c] = true;
for (int k = 0; k < 4; k++) {
int nr = r + DR[k], nc = c + DC[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && maze[nr][nc] == 1 && !seen[nr][nc]) {
path.append(NAME[k]);
go(maze, nr, nc, seen, path, paths);
path.deleteCharAt(path.length() - 1); // step back
}
}
seen[r][c] = false; // free this cell for other paths
}
}How long it takes: after the first step a mouse has at most 3 new hallways (it never goes straight back), and a trip can be up to N^2 squares long, so the search is O(3^(N^2)) in the worst case. Sorting P trips of up to N^2 letters adds O(P * N^2 * log P). Extra room: the seen board and the recursion, O(N^2).
Way 2: the clever way
Use the chalk. Try directions in the order D, L, R, U, which is dictionary order. Then the trips come out sorted and no sort is needed. Mark squares by writing 0 on the maze itself and putting the 1 back on the way out, so no extra board is needed. This walk-and-undo method is backtracking.
- If the start or the cheese is a wall, return nothing.
- Stand on a square: chalk it (set it to 0).
- Try D, L, R, U. Step into any square that is still
1. - At the cheese, save the trip. Coming back, wipe the chalk (set it back to 1).
The mouse tries D, L, R, U and wipes its chalk on the way back
01 / 09
Start at S and chalk it. Try Down first: the square below is open, so step there.
- looking now
- answer
- rejected
- path
- ignored
class MazeSorted {
// try moves in alphabetical order: D, L, R, U
static final int[] DR = {1, 0, 0, -1};
static final int[] DC = {0, -1, 1, 0};
static final char[] NAME = {'D', 'L', 'R', 'U'};
public static List<String> findPaths(int[][] maze) {
int n = maze.length;
List<String> paths = new ArrayList<>();
if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return paths;
go(maze, 0, 0, new StringBuilder(), paths);
return paths; // already sorted, no sort needed
}
static void go(int[][] maze, int r, int c, StringBuilder path, List<String> paths) {
int n = maze.length;
if (r == n - 1 && c == n - 1) { paths.add(path.toString()); return; }
maze[r][c] = 0; // chalk mark: block it while we stand on the path
for (int k = 0; k < 4; k++) {
int nr = r + DR[k], nc = c + DC[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && maze[nr][nc] == 1) {
path.append(NAME[k]);
go(maze, nr, nc, path, paths);
path.deleteCharAt(path.length() - 1);
}
}
maze[r][c] = 1; // wipe the chalk on the way back
}
}How long it takes: the same search, O(3^(N^2)) in the worst case, but with no sorting step and no extra board. Listing every trip cannot be fast in general, because the number of trips itself can be that large. Extra room: the recursion is at most N^2 deep, O(N^2), not counting the answer.
Another way: only the shortest trip
If the question asks for the shortest trip, do not list them all. Spread out in rings from the start with a waiting line (breadth first search). Remember which move first reached each square, then walk those moves back from the cheese. This takes O(N^2) time and room.
class MazeShortest {
public static String shortestPath(int[][] maze) {
int n = maze.length;
if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return "-1";
int[] dr = {1, 0, 0, -1};
int[] dc = {0, -1, 1, 0};
char[] name = {'D', 'L', 'R', 'U'};
int[][] how = new int[n][n]; // which move first reached this cell
for (int[] row : how) Arrays.fill(row, -1);
how[0][0] = 4; // the start, reached by no move
Queue<int[]> line = new ArrayDeque<>();
line.add(new int[]{0, 0});
while (!line.isEmpty()) {
int[] cur = line.poll();
if (cur[0] == n - 1 && cur[1] == n - 1) break;
for (int k = 0; k < 4; k++) {
int r = cur[0] + dr[k], c = cur[1] + dc[k];
if (r >= 0 && r < n && c >= 0 && c < n && maze[r][c] == 1 && how[r][c] == -1) {
how[r][c] = k;
line.add(new int[]{r, c});
}
}
}
if (how[n - 1][n - 1] == -1) return "-1";
StringBuilder sb = new StringBuilder();
int r = n - 1, c = n - 1;
while (how[r][c] != 4) { // walk the moves back to the start
int k = how[r][c];
sb.append(name[k]);
r -= dr[k];
c -= dc[k];
}
return sb.reverse().toString();
}
}Watch out for
- Check that the start and the cheese are open before searching.
- Do not stop at the first trip when the question asks for all of them.
- In the shortest trip version, mark a square when it joins the line, not when it leaves.
- Building a new string at every square (
path + "D") works but copies a lot. AStringBuilderwith append and delete is cheaper.
What interviewers ask next
- The mouse can also move diagonally. Add 4 more moves; nothing else changes.
- Count the trips without listing them. Same backtracking, but add 1 at the cheese instead of saving a string. If moves are only Down and Right, a counting table (dynamic programming) does it in
O(N^2). - Find the shortest trip when squares have different costs. Use Dijkstra's algorithm with a heap instead of a plain waiting line.
- Some squares let the mouse jump several squares (the number on the square). Loop over the jump length in the same backtracking.
Remember this
Grown-up words: the maze is a grid graph, the mouse's walk is depth first search, walk-and-undo is backtracking, the chalk is the visited mark, the tree of choices is the recursion tree, and the waiting line in the shortest version is breadth first search.