Find shortest safe route in a path with landmines

Cross a field from the left edge to the right edge in the fewest steps, never stepping on a mine or right next to one.

Simple way: time O(4^(m*n))
room O(m*n)
Clever way: time O(m*n)
room O(m*n)

The problem, simply

You get a grid of cells. A 0 is a landmine and a 1 is ground. A cell right next to a mine (up, down, left or right) is also unsafe, because the mine could go off.

Start from any safe cell in the first column and reach any cell in the last column. You may step up, down, left or right, and only onto safe cells. Give back the fewest steps needed, or -1 if there is no safe way across.

A story to remember it

Picture it

grid

M is a mine. x marks a cell next to a mine, which is also unsafe. The blank cells are safe. The route has to snake around both groups of mines.

rejected
ignored

Examples

The field above

In: 5 by 6 field with mines at (0,2), (0,4), (2,4), (4,1)
Out: 7

Start at (2,0), go right to (2,2), down to (3,2), right to (3,3), down to (4,3), then right to (4,5). That is 7 steps.

No mines at all

In: 3 by 4 field of all 1s
Out: 3

Walk straight across. Four columns need three steps.

A wall of danger

In: [[1, 0, 1], [1, 1, 1], [1, 0, 1]]
Out: -1

Column 1 has a mine at the top and bottom, and the middle cell touches both. No safe way through, so return -1.

One column

In: [[1], [1]]
Out: 0

The first column is also the last column. You are already there.

Way 1: the simple way

First mark every unsafe cell. Then from each safe cell in the first column, try every walk, like a rat in a maze, and keep the shortest one that reaches the last column.

Make a safe grid: a cell is safe if it is ground and none of its four neighbors is a mine.
From each safe start, walk in all four directions to safe cells not on the current walk.
When you reach the last column, keep the walk length if it is the best so far.
If the current walk is already as long as the best, stop early.
On the way back, take the cell off the walk.

java

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 shortestSafeRoute(int[][] mat) {
        boolean[][] safe = markSafe(mat);
        int m = mat.length, n = mat[0].length;
        best = Integer.MAX_VALUE;
        boolean[][] onWalk = new boolean[m][n];
        for (int r = 0; r < m; r++) {
            if (safe[r][0]) walk(safe, r, 0, 0, onWalk);
        }
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    private void walk(boolean[][] safe, int r, int c, int steps, boolean[][] onWalk) {
        if (steps >= best) return;                    // cannot beat the best any more
        if (c == safe[0].length - 1) { best = steps; return; }
        onWalk[r][c] = true;
        for (int d = 0; d < 4; d++) {
            int nr = r + DR[d], nc = c + DC[d];
            if (nr >= 0 && nr < safe.length && nc >= 0 && nc < safe[0].length
                    && safe[nr][nc] && !onWalk[nr][nc]) {
                walk(safe, nr, nc, steps + 1, onWalk);
            }
        }
        onWalk[r][c] = false;                         // step back
    }

    static boolean[][] markSafe(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        boolean[][] safe = new boolean[m][n];
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) safe[r][c] = mat[r][c] == 1;
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                if (mat[r][c] == 0)
                    for (int d = 0; d < 4; d++) {
                        int nr = r + DR[d], nc = c + DC[d];
                        if (nr >= 0 && nr < m && nc >= 0 && nc < n) safe[nr][nc] = false;
                    }
        return safe;
    }
}

How long it takes: the number of walks can grow like 4^(m*n) in a wide open field, so this is exponential. Extra room: the marks and the call stack, O(m*n).

Way 2: the clever way

All steps cost the same. When that is true, the shortest way is found by spreading out in rings: everyone one step away, then everyone two steps away, and so on. That spreading uses a waiting line, a queue. Putting all the first column cells in the line at the start lets every starting kid race at once.

Build the safe grid as before.
Put every safe cell of column 0 in the line with distance 0.
Take a cell from the front. If it is in the last column, its distance is the answer.
Otherwise give each safe, unseen neighbor distance plus one, and put it at the back.
If the line empties first, return -1.

A cell is seen once and never again, so there is no undoing here. That is the big difference from Way 1.

Spread out one step at a time from the left edge

01 / 09

grid

queuewaiting line (row,col)

M is a mine. A cell next to a mine is unsafe too, so it shows x. The safe cells in column 0 are rows 0 to 3. They all join the waiting line with distance 0.

step: 0

seen
answer
rejected
just added
ignored

java

import java.util.*;

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

    public int shortestSafeRoute(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        boolean[][] safe = new boolean[m][n];
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) safe[r][c] = mat[r][c] == 1;
        for (int r = 0; r < m; r++)                   // a mine makes its neighbors unsafe
            for (int c = 0; c < n; c++)
                if (mat[r][c] == 0)
                    for (int d = 0; d < 4; d++) {
                        int nr = r + DR[d], nc = c + DC[d];
                        if (nr >= 0 && nr < m && nc >= 0 && nc < n) safe[nr][nc] = false;
                    }

        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, -1);
        Queue<int[]> line = new ArrayDeque<>();
        for (int r = 0; r < m; r++) {
            if (safe[r][0]) {                         // every left edge cell starts at once
                dist[r][0] = 0;
                line.add(new int[]{r, 0});
            }
        }

        while (!line.isEmpty()) {
            int[] cell = line.poll();
            int r = cell[0], c = cell[1];
            if (c == n - 1) return dist[r][c];        // first to the right edge is shortest
            for (int d = 0; d < 4; d++) {
                int nr = r + DR[d], nc = c + DC[d];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n
                        && safe[nr][nc] && dist[nr][nc] == -1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    line.add(new int[]{nr, nc});
                }
            }
        }
        return -1;
    }
}

How long it takes: each cell joins the line at most once and looks at 4 neighbors, O(m*n). Extra room: the safe grid, the distances and the line, O(m*n).

Watch out for

Starting the search from only one cell of the first column. Every safe cell there is a valid start, so put them all in the line.
Checking for the last column when you add a cell instead of when you take it out is fine too, but then also check the starting cells, for a grid with one column.
Counting cells instead of steps. Say which one you return. Here a route of 8 cells is 7 steps.
Forgetting that the start cell itself must be safe, not only ground.

What interviewers ask next

Print the route, not only its length. Store, for each cell, the cell it was reached from, then walk those back from the finish.
What if stepping onto some cells costs more, like mud? Then rings no longer work. Use Dijkstra with a priority queue.
What if moves can also go diagonally, or mines also make diagonal cells unsafe? Use 8 directions in the right place. The search stays the same.
Can you skip the extra safe grid? Yes, mark unsafe cells as -1 in the input during one pass, then treat only 1 as walkable. Say that you are changing the input.

Remember this

Grown-up words: the field is a grid graph, spreading out in rings is breadth first search, starting from many cells at once is multi source BFS, the waiting line is a queue, and Way 1 is backtracking over all simple paths.