Escape the Spreading Fire

Hard Graphs Multi source BFS Original on LeetCode

Reported atUber

Escape the Spreading Fire is a hard graphs problem solved with the multi source bfs pattern. The best approach, optimal (two bfs and compare arrival times), runs in O(m · n) time and O(m · n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try every waiting time) up.

Problem

You are standing in the top-left cell (0, 0) of an m x n field and want to reach the safehouse in the bottom-right cell (m - 1, n - 1). Each cell of grid is 0 (grass you can walk on), 1 (burning) or 2 (a wall that neither you nor the fire can pass).

You may first stay at the start for some whole number of minutes. After that, every minute you step to an adjacent grass cell (up, down, left or right), and then the fire spreads from every burning cell to every adjacent grass cell. You lose if the fire reaches the cell you are on, including the moment right after you step into it. The only exception is the safehouse: reaching it in the same minute as the fire still counts as safe.

Return the largest number of minutes you can wait at the start and still reach the safehouse safely. Return -1 if escaping is impossible even without waiting, and 10^9 if you can escape no matter how long you wait.

Examples

Example 1

Input
grid = [[0,0,0,0],[0,2,0,0],[0,2,0,0],[1,2,0,0]]
Output
2
Why
Fire climbs the left column, reaching the start at minute 3 and the safehouse at minute 9. Leaving after 2 minutes you arrive at minute 8, ahead of the fire on every cell; waiting 3 minutes would burn you at the start.

Example 2

Input
grid = [[0,0,0],[2,2,0],[1,2,0]]
Output
1000000000
Why
The fire at the bottom-left is sealed in by walls, so you can wait as long as you like.

Example 3

Input
grid = [[0,1,0],[0,0,0],[0,0,0]]
Output
-1
Why
The fire reaches the safehouse after 3 minutes, but the shortest walk there takes 4, so even leaving at once is too late.

Constraints

  • m == grid.length, n == grid[i].length
  • 2 <= m, n <= 300 and 4 <= m * n <= 2 * 10^4
  • grid[i][j] is 0 (grass), 1 (fire) or 2 (wall).
  • grid[0][0] == grid[m - 1][n - 1] == 0

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 19 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every waiting time)O((m · n)²)O(m · n)
Binary search on the waiting timeO(m · n · log(m · n))O(m · n)
Optimal (two BFS and compare arrival times)O(m · n)O(m · n)

1Brute force (try every waiting time)

TimeO((m · n)²)Up to m · n + 1 waiting times, each checked with an O(m · n) BFS.
SpaceO(m · n)The fire-time grid plus one BFS queue and visited grid.

Compute the fire arrival times once. Then try waiting w = 0, 1, 2, ... and run a BFS for each w to see whether you can still escape. Once fire has had m · n minutes it can no longer spread, so if waiting m · n minutes still works you can wait forever.

  1. Multi-source BFS from all fire cells gives fire[r][c] (infinity if never burned).
  2. check(w): you are at the start at minute w (fail if fire[0][0] <= w). BFS; a grass cell may be entered at minute t if fire > t, the safehouse if fire >= t.
  3. For w from 0 to m · n: the first failing w gives answer w - 1. If none fails, return 10^9.
class Solution {
    static final int INF = Integer.MAX_VALUE;
    static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    private int[][] fireTimes(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] fire = new int[m][n];
        Deque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                fire[i][j] = INF;
                if (grid[i][j] == 1) {
                    fire[i][j] = 0;
                    q.add(new int[] { i, j });
                }
            }
        while (!q.isEmpty()) {
            int[] c = q.poll();
            for (int[] d : DIRS) {
                int r = c[0] + d[0], k = c[1] + d[1];
                if (r < 0 || k < 0 || r >= m || k >= n || grid[r][k] != 0 || fire[r][k] != INF) continue;
                fire[r][k] = fire[c[0]][c[1]] + 1;
                q.add(new int[] { r, k });
            }
        }
        return fire;
    }

    private boolean canEscape(int[][] grid, int[][] fire, int w) {
        int m = grid.length, n = grid[0].length;
        if (fire[0][0] <= w) return false;
        int[][] time = new int[m][n];
        for (int[] row : time) Arrays.fill(row, -1);
        time[0][0] = w;
        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[] { 0, 0 });
        while (!q.isEmpty()) {
            int[] c = q.poll();
            int t = time[c[0]][c[1]] + 1;
            for (int[] d : DIRS) {
                int r = c[0] + d[0], k = c[1] + d[1];
                if (r < 0 || k < 0 || r >= m || k >= n || grid[r][k] != 0 || time[r][k] != -1) continue;
                if (r == m - 1 && k == n - 1) {
                    if (fire[r][k] >= t) return true;
                    continue;
                }
                if (fire[r][k] <= t) continue;
                time[r][k] = t;
                q.add(new int[] { r, k });
            }
        }
        return false;
    }

    public int maximumMinutes(int[][] grid) {
        int[][] fire = fireTimes(grid);
        int limit = grid.length * grid[0].length;
        for (int w = 0; w <= limit; w++) {
            if (!canEscape(grid, fire, w)) return w - 1;
        }
        return 1000000000;
    }
}

2Binary search on the waiting time

TimeO(m · n · log(m · n))About log(m · n) checks, each an O(m · n) BFS.
SpaceO(m · n)Fire-time grid plus the BFS state.

If you can escape after waiting w minutes, you can also escape after waiting less, so feasibility is monotone. Binary search the largest feasible w in [0, m · n] using the same BFS check.

  1. Compute fire times with a multi-source BFS.
  2. If check(0) fails, return -1. If check(m · n) succeeds, return 10^9.
  3. Binary search the largest w with check(w) true and return it.
class Solution {
    static final int INF = Integer.MAX_VALUE;
    static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    private int[][] fireTimes(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] fire = new int[m][n];
        Deque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                fire[i][j] = INF;
                if (grid[i][j] == 1) {
                    fire[i][j] = 0;
                    q.add(new int[] { i, j });
                }
            }
        while (!q.isEmpty()) {
            int[] c = q.poll();
            for (int[] d : DIRS) {
                int r = c[0] + d[0], k = c[1] + d[1];
                if (r < 0 || k < 0 || r >= m || k >= n || grid[r][k] != 0 || fire[r][k] != INF) continue;
                fire[r][k] = fire[c[0]][c[1]] + 1;
                q.add(new int[] { r, k });
            }
        }
        return fire;
    }

    private boolean canEscape(int[][] grid, int[][] fire, int w) {
        int m = grid.length, n = grid[0].length;
        if (fire[0][0] <= w) return false;
        int[][] time = new int[m][n];
        for (int[] row : time) Arrays.fill(row, -1);
        time[0][0] = w;
        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[] { 0, 0 });
        while (!q.isEmpty()) {
            int[] c = q.poll();
            int t = time[c[0]][c[1]] + 1;
            for (int[] d : DIRS) {
                int r = c[0] + d[0], k = c[1] + d[1];
                if (r < 0 || k < 0 || r >= m || k >= n || grid[r][k] != 0 || time[r][k] != -1) continue;
                if (r == m - 1 && k == n - 1) {
                    if (fire[r][k] >= t) return true;
                    continue;
                }
                if (fire[r][k] <= t) continue;
                time[r][k] = t;
                q.add(new int[] { r, k });
            }
        }
        return false;
    }

    public int maximumMinutes(int[][] grid) {
        int[][] fire = fireTimes(grid);
        int limit = grid.length * grid[0].length;
        if (!canEscape(grid, fire, 0)) return -1;
        if (canEscape(grid, fire, limit)) return 1000000000;
        int lo = 0, hi = limit - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (canEscape(grid, fire, mid)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }
}

3Optimal (two BFS and compare arrival times)

TimeO(m · n)Two BFS passes over the grid, then O(1) work.
SpaceO(m · n)Two distance grids and a queue.

Run one BFS for the fire and one for yourself (no waiting, grass cells only). Let d = fire[safe] - you[safe]. Walking a shortest path after waiting w, the fire can only catch you if it also reaches the safehouse by then, so d is an upper bound. The only subtlety is a tie: arriving together is fine at the safehouse but fatal one step earlier. So the answer is d if one of the two neighbours of the safehouse (above or left) is reached with slack fire - you > d, and d - 1 otherwise.

  1. BFS from all fire cells gives fire; BFS from (0, 0) over grass gives you (infinity if unreachable).
  2. If you[safe] is infinite, return -1. If fire[safe] is infinite, return 10^9.
  3. d = fire[safe] - you[safe]; if d < 0, return -1.
  4. For the neighbours above and to the left of the safehouse that you can reach, compute fire - you (infinite fire counts as huge). If any slack is > d, return d; otherwise return d - 1.
class Solution {
    static final int INF = Integer.MAX_VALUE;
    static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    private int[][] bfs(int[][] grid, List<int[]> sources) {
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, INF);
        Deque<int[]> q = new ArrayDeque<>();
        for (int[] s : sources) {
            dist[s[0]][s[1]] = 0;
            q.add(s);
        }
        while (!q.isEmpty()) {
            int[] c = q.poll();
            for (int[] d : DIRS) {
                int r = c[0] + d[0], k = c[1] + d[1];
                if (r < 0 || k < 0 || r >= m || k >= n || grid[r][k] != 0 || dist[r][k] != INF) continue;
                dist[r][k] = dist[c[0]][c[1]] + 1;
                q.add(new int[] { r, k });
            }
        }
        return dist;
    }

    private long slack(int[][] fire, int[][] you, int r, int c) {
        if (you[r][c] == INF) return Long.MIN_VALUE;
        if (fire[r][c] == INF) return Long.MAX_VALUE;
        return (long) fire[r][c] - you[r][c];
    }

    public int maximumMinutes(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        List<int[]> fires = new ArrayList<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) fires.add(new int[] { i, j });
        int[][] fire = bfs(grid, fires);
        int[][] you = bfs(grid, List.of(new int[] { 0, 0 }));
        if (you[m - 1][n - 1] == INF) return -1;
        if (fire[m - 1][n - 1] == INF) return 1000000000;
        int d = fire[m - 1][n - 1] - you[m - 1][n - 1];
        if (d < 0) return -1;
        if (slack(fire, you, m - 2, n - 1) > d || slack(fire, you, m - 1, n - 2) > d) return d;
        return d - 1;
    }
}

Edge cases to test

  • No fire at all: the answer is 10^9 as long as the safehouse is reachable
  • The safehouse is walled off: -1 regardless of fire
  • Fire and you reach the safehouse at the same minute: allowed
  • Fire catches you one step before the safehouse (arriving together at an ordinary cell is fatal)
  • Fire that is sealed in by walls and never spreads

Hints

Hint 1

First compute, with one multi-source BFS from every fire cell, the minute at which fire reaches each grass cell.

Hint 2

For a fixed waiting time w you can check feasibility with a BFS for yourself that only enters a cell strictly before the fire arrives (the safehouse may be entered at the same minute). Feasibility is monotone in w, so you can binary search.

Hint 3

Even better: compare your shortest arrival time at the safehouse with the fire's. The difference d is the answer or d - 1; it is d only if one of the safehouse's two neighbours (above or left) lets you stay strictly ahead of the fire there as well.

FAQ

What is the best time complexity for Escape the Spreading Fire?

Optimal (two BFS and compare arrival times) runs in O(m · n) time and O(m · n) extra space. Two BFS passes over the grid, then O(1) work.

Which pattern does Escape the Spreading Fire use?

It is a graphs problem that uses the multi source bfs pattern. Other problems with the same pattern: Rotting Oranges, 01 Matrix, Pacific Atlantic Water Flow.

Is there a brute force solution for Escape the Spreading Fire?

Yes. Brute force (try every waiting time) takes O((m · n)²) time and O(m · n) space. Compute the fire arrival times once.

Which edge cases should I test for Escape the Spreading Fire?

No fire at all: the answer is 10^9 as long as the safehouse is reachable; The safehouse is walled off: -1 regardless of fire; Fire and you reach the safehouse at the same minute: allowed; Fire catches you one step before the safehouse (arriving together at an ordinary cell is fatal); Fire that is sealed in by walls and never spreads.