Rat in a maze Problem

The problem, simply

You get an n by n maze. A 1 is an open cell and a 0 is a wall. A rat starts at the top left cell and wants to reach the bottom right cell. It can move down (D), left (L), right (R) or up (U), and it may not step on a cell twice in one path.

Give back every path as a string of moves, in dictionary order. If there is no path, give back an empty list.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk every route, and give each step its own fresh copy of the breadcrumb map. That way nothing has to be cleaned up afterwards. At the end, sort the answers.

1. If the rat is at the exit, save the moves.
2. Copy the breadcrumb map and drop a crumb on the current cell in the copy.
3. Try all four moves into open cells without crumbs, passing the copy and the moves plus one letter.
4. Sort the saved paths.

import java.util.*;

class Solution {
    public List<String> findPath(int[][] maze) {
        int n = maze.length;
        List<String> result = new ArrayList<>();
        if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return result;
        walk(maze, 0, 0, "", new boolean[n][n], result);
        Collections.sort(result);                         // dictionary order at the end
        return result;
    }

    private void walk(int[][] maze, int r, int c, String path, boolean[][] crumbs, List<String> result) {
        int n = maze.length;
        if (r == n - 1 && c == n - 1) {
            result.add(path);
            return;
        }
        boolean[][] mine = new boolean[n][n];             // a fresh copy for this step
        for (int i = 0; i < n; i++) mine[i] = crumbs[i].clone();
        mine[r][c] = true;
        int[][] moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        char[] names = {'U', 'D', 'L', 'R'};
        for (int k = 0; k < 4; k++) {
            int nr = r + moves[k][0], nc = c + moves[k][1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && maze[nr][nc] == 1 && !mine[nr][nc]) {
                walk(maze, nr, nc, path + names[k], mine, result);
            }
        }
    }
}

How long it takes: after the first step, each cell has at most 3 new ways to go (not back where it came from), and a path can be n^2 cells long, so up to 3^(n^2) routes. Each step also copies an n by n map, so O(3^(n^2) * n^2). Extra room: one map copy per level, and there can be n^2 levels, so O(n^4).

Way 2: the clever way

Use one breadcrumb map for the whole search. Drop a crumb when you step on a cell and pick it up when you step back. Also try the moves in the order D, L, R, U, which is dictionary order, so the answers come out already sorted.

1. If the rat is at the exit, save the moves.
2. Mark the current cell, for example by turning it into a wall for now.
3. For each move in the order D, L, R, U: if the next cell is open, add the letter, walk, and remove the letter.
4. Unmark the current cell before returning.

import java.util.*;

class Solution {
    private static final int[] DR = {1, 0, 0, -1};       // D, L, R, U: dictionary order
    private static final int[] DC = {0, -1, 1, 0};
    private static final char[] NAME = {'D', 'L', 'R', 'U'};

    public List<String> findPath(int[][] maze) {
        int n = maze.length;
        List<String> result = new ArrayList<>();
        if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return result;
        walk(maze, 0, 0, new StringBuilder(), result);
        return result;                                   // already sorted
    }

    private void walk(int[][] maze, int r, int c, StringBuilder path, List<String> result) {
        int n = maze.length;
        if (r == n - 1 && c == n - 1) {
            result.add(path.toString());
            return;
        }
        maze[r][c] = 0;                                  // drop a crumb: my cell is a wall for now
        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]);
                walk(maze, nr, nc, path, result);
                path.deleteCharAt(path.length() - 1);
            }
        }
        maze[r][c] = 1;                                  // pick the crumb back up
    }
}

How long it takes: the same search tree, O(3^(n^2)) in the worst case, but no map copies, and no sorting. Extra room: the call stack and the path can be n^2 long, O(n^2).

Watch out for

• Forgetting to check that the start and the exit are open.
• Marking the exit. You stop when you get there, so it must stay open for the next route.
• Changing the input maze. Way 2 restores every cell, so the maze is the same at the end, but say that you borrow it.
• Trying moves in a random order and then forgetting to sort. Use D, L, R, U.

What interviewers ask next

• Only the shortest path length. Use breadth first search from the start, O(n^2). Backtracking is only needed to list every path.
• The rat can only move right and down. Then no cell can be visited twice, so no marks are needed, and counting paths becomes a simple table.
• Some cells let the rat jump several cells at once. Same search, but the moves come from the number in the cell.
• Count paths in a big maze. The count can be huge and the search is exponential. Ask for limits. For up to about 7 by 7 it is fine.

Remember this

Grown-up words: the maze is a grid graph, the crumbs are a visited array, picking them up is backtracking, and the route strings are paths in a depth first search.