Longest Possible Route in a Matrix with Hurdles

The problem, simply

You get a grid. A 1 is open ground and a 0 is a hurdle you cannot step on. You also get a start cell and a goal cell.

Walk from the start to the goal, one step at a time up, down, left or right. You may not step on any cell twice. Give back the number of steps in the longest such route, or -1 if the goal cannot be reached at all.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every route. Mark a cell when you step on it and unmark it when you step back, so other routes can use it.

1. If you are on the goal, compare the steps with the best and stop this route.
2. Mark the current cell as used.
3. Try each of the 4 neighbors that is inside the grid, open, and not used.
4. Unmark the current cell before going back.

class Solution {
    private static final int[] DR = {-1, 0, 1, 0};
    private static final int[] DC = {0, 1, 0, -1};
    private int best;

    public int longestPath(int[][] mat, int sr, int sc, int tr, int tc) {
        if (mat[sr][sc] == 0 || mat[tr][tc] == 0) return -1;
        best = -1;
        walk(mat, sr, sc, tr, tc, 0, new boolean[mat.length][mat[0].length]);
        return best;
    }

    private void walk(int[][] mat, int r, int c, int tr, int tc, int steps, boolean[][] used) {
        if (r == tr && c == tc) {                  // home: keep the longest
            best = Math.max(best, steps);
            return;
        }
        used[r][c] = true;
        for (int d = 0; d < 4; d++) {
            int nr = r + DR[d], nc = c + DC[d];
            if (nr >= 0 && nr < mat.length && nc >= 0 && nc < mat[0].length
                    && mat[nr][nc] == 1 && !used[nr][nc]) {
                walk(mat, nr, nc, tr, tc, steps + 1, used);
            }
        }
        used[r][c] = false;                        // step back, free the cell
    }
}

How long it takes: each cell offers up to 4 ways on, and a route can touch all m * n cells, so the count of routes can grow like 4^(m*n). On the classic 3 by 10 example it makes 1881 calls. Extra room: the used marks and the call stack, O(m*n).

Way 2: the clever way

Keep the same search, but before going deeper, look at the room you have left. Flood out from where you stand, over open cells that are not used yet, and count them.

1. If the goal is not in that flood, your own path has cut you off. Stop this branch.
2. If steps + room is not more than the best, even a perfect route from here cannot win. Stop this branch.
3. Otherwise try the 4 neighbors as before.

This is called branch and bound: a quick upper bound tells you when a whole branch is hopeless.

import java.util.*;

class Solution {
    private static final int[] DR = {-1, 0, 1, 0};
    private static final int[] DC = {0, 1, 0, -1};
    private int best;

    public int longestPath(int[][] mat, int sr, int sc, int tr, int tc) {
        if (mat[sr][sc] == 0 || mat[tr][tc] == 0) return -1;
        best = -1;
        walk(mat, sr, sc, tr, tc, 0, new boolean[mat.length][mat[0].length]);
        return best;
    }

    private void walk(int[][] mat, int r, int c, int tr, int tc, int steps, boolean[][] used) {
        if (r == tr && c == tc) {
            best = Math.max(best, steps);
            return;
        }
        used[r][c] = true;
        int room = roomLeft(mat, r, c, tr, tc, used);   // -1 means the goal is cut off
        if (room >= 0 && steps + room > best) {         // only go on if we can still win
            for (int d = 0; d < 4; d++) {
                int nr = r + DR[d], nc = c + DC[d];
                if (open(mat, nr, nc) && !used[nr][nc]) {
                    walk(mat, nr, nc, tr, tc, steps + 1, used);
                }
            }
        }
        used[r][c] = false;
    }

    // count open, unused cells we can still reach from (r, c); -1 if the goal is not one of them
    private int roomLeft(int[][] mat, int r, int c, int tr, int tc, boolean[][] used) {
        boolean[][] seen = new boolean[mat.length][mat[0].length];
        Deque<int[]> todo = new ArrayDeque<>();
        todo.push(new int[]{r, c});
        seen[r][c] = true;
        int count = 0;
        boolean goal = false;
        while (!todo.isEmpty()) {
            int[] cell = todo.pop();
            for (int d = 0; d < 4; d++) {
                int nr = cell[0] + DR[d], nc = cell[1] + DC[d];
                if (open(mat, nr, nc) && !used[nr][nc] && !seen[nr][nc]) {
                    seen[nr][nc] = true;
                    count++;
                    if (nr == tr && nc == tc) goal = true;
                    todo.push(new int[]{nr, nc});
                }
            }
        }
        return goal ? count : -1;
    }

    private boolean open(int[][] mat, int r, int c) {
        return r >= 0 && r < mat.length && c >= 0 && c < mat[0].length && mat[r][c] == 1;
    }
}

How long it takes: the worst case is still exponential, O(4^(m*n)), and each call now spends O(m*n) on the flood. But far fewer calls happen. On the classic 3 by 10 example it drops from 1881 calls to 710, and on an open 5 by 6 grid with two hurdles from about 36000 to about 4000. Extra room: O(m*n) for the marks, the flood and the call stack.

Why not something fast, like breadth first search? Breadth first search finds the shortest route. The longest route without repeats is a famous hard problem (NP-hard), so every known exact method is exponential in the worst case.

Watch out for

• Counting cells instead of steps. A route through 7 cells has 6 steps. Say which one you return.
• Forgetting to check that the start and the goal are open.
• Marking the goal as used. You stop as soon as you reach it, so it never needs a mark.
• Stopping at the first route that reaches the goal. The first route is often the short one.

What interviewers ask next

• Why does breadth first search not work? It always finds the fewest steps first. To find the most steps you would need to remember which cells each route used, and there are too many such sets.
• Can you use memoization? Not on the cell alone, because the answer depends on which cells are already used. You can memo on (cell, used set) with a bitmask if the grid has at most about 20 open cells.
• Can you prune more? A grid is like a checkerboard: every step changes the color. So the number of steps from start to goal is always even or always odd, which can tighten the bound by one.
• Print the route. Keep a list of cells, add on mark, remove on unmark, and copy it whenever you beat the best.

Remember this

Grown-up words: the grid is a grid graph, the route is a simple path, marking and unmarking is backtracking, the flood is a depth first search for reachability, and stopping hopeless branches with a bound is branch and bound.