Escape the Spreading Fire — Hard Problem & Solution
A grid holds 0 for grass, 1 for fire and 2 for a wall. You start at the top-left cell and want to reach the safehouse at the bottom-right.
- Difficulty: Hard
- Topics: Arrays, Matrix, Binary Search, Breadth-First Search
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A grid holds 0 for grass, 1 for fire and 2 for a wall. You start at the top-left cell and want to reach the safehouse at the bottom-right.
Each minute you may move one cell up, down, left or right onto grass, and then the fire spreads to every grass cell adjacent to a burning one. Walls block both of you. You may first wait in place for some minutes before setting off — but not while your cell is on fire.
Return the maximum number of minutes you can wait and still reach the safehouse, or -1 if you cannot reach it even without waiting. If you can wait forever, return 10^9.
Reaching the safehouse at the very minute the fire arrives there still counts as escaping.
Example 1
Input: grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]
Output: 3Example 2
Input: grid = [[0,0,0,0],[0,1,2,0],[0,2,2,0],[0,0,0,0]]
Output: -1
Explanation: The fire reaches every route before you do.Example 3
Input: grid = [[0,0,0],[2,2,0],[1,2,0]]
Output: 1000000000
Explanation: Walls pen the fire in, so it never spreads.Constraints
m == grid.lengthn == grid[i].length2 <= m, n <= 3004 <= m * n <= 2 * 10^4grid[i][j] is 0, 1 or 2grid[0][0] == grid[m-1][n-1] == 0
How to solve Escape the Spreading Fire
Precompute the fire's arrival time everywhere, then binary search the wait. For a candidate wait, one BFS decides whether a safe route exists.
Approach
- Multi-source BFS from the fire cells through grass only, giving
fire[cell]. canEscape(t): BFS from the start with clock beginning att; step onto a cell only ifarrival < fire[cell].- At the safehouse, accept
arrival <= fire[cell]instead. - Binary search the largest
tin[0, m·n]. If evenm·nworks, the fire can never catch you — return10^9; if0fails, return-1.
Why it works
Monotonicity is what makes the binary search valid: the route that works after waiting t also works after waiting less, since every arrival time only shrinks while the fire's schedule is fixed. And m·n is a safe upper bound — a route has at most m·n cells, so if waiting that long still works, no reachable cell is ever on fire ahead of you.
Complexity
- Time —
O(m · n · log(m · n)) - Space —
O(m · n)
Pitfalls
- The safehouse's
<=rule is a genuine special case; using<there loses cases. - Cells the fire never reaches need an infinite arrival time, not zero.
- You cannot wait on a burning start cell, so
canEscape(t)must rejectt >= fire[start].
Reference solution
Python
from typing import List
from collections import deque
def maximumMinutes(grid: List[List[int]]) -> int:
BIG = 1000000000
m, n = len(grid), len(grid[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
fire = [[BIG] * n for _ in range(m)]
q = deque()
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
fire[i][j] = 0
q.append((i, j))
while q:
r, c = q.popleft()
for di, dj in dirs:
nr, nc = r + di, c + dj
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != 2 and fire[nr][nc] == BIG:
fire[nr][nc] = fire[r][c] + 1
q.append((nr, nc))
def can_escape(wait: int) -> bool:
if fire[0][0] <= wait:
return False
seen = [[False] * n for _ in range(m)]
seen[0][0] = True
bq = deque([(0, 0, wait)])
while bq:
r, c, t = bq.popleft()
for di, dj in dirs:
nr, nc = r + di, c + dj
if not (0 <= nr < m and 0 <= nc < n) or grid[nr][nc] == 2 or seen[nr][nc]:
continue
at = t + 1
if nr == m - 1 and nc == n - 1:
if fire[nr][nc] >= at:
return True
continue
if fire[nr][nc] <= at:
continue
seen[nr][nc] = True
bq.append((nr, nc, at))
return False
if not can_escape(0):
return -1
hi = m * n
if can_escape(hi):
return BIG
lo = 0
while lo < hi:
mid = lo + (hi - lo + 1) // 2
if can_escape(mid):
lo = mid
else:
hi = mid - 1
return loJavaScript
var maximumMinutes = function(grid) {
var BIG = 1000000000;
var m = grid.length, n = grid[0].length, i, j, d;
var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
var fire = [];
for (i = 0; i < m * n; i++) fire.push(BIG);
var q = [];
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
if (grid[i][j] === 1) { fire[i * n + j] = 0; q.push(i * n + j); }
}
}
var head = 0;
while (head < q.length) {
var cur = q[head++];
var r = Math.floor(cur / n), c = cur % n;
for (d = 0; d < 4; d++) {
var nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
var key = nr * n + nc;
if (grid[nr][nc] === 2 || fire[key] < BIG) continue;
fire[key] = fire[cur] + 1;
q.push(key);
}
}
var canEscape = function(wait) {
if (fire[0] <= wait) return false;
var seen = [], time = [];
for (var t = 0; t < m * n; t++) { seen.push(false); time.push(0); }
seen[0] = true;
time[0] = wait;
var bq = [0], h = 0;
while (h < bq.length) {
var cur2 = bq[h++];
var r2 = Math.floor(cur2 / n), c2 = cur2 % n;
for (var dd = 0; dd < 4; dd++) {
var ar = r2 + dr[dd], ac = c2 + dc[dd];
if (ar < 0 || ar >= m || ac < 0 || ac >= n) continue;
var k = ar * n + ac;
if (grid[ar][ac] === 2 || seen[k]) continue;
var at = time[cur2] + 1;
if (ar === m - 1 && ac === n - 1) {
if (fire[k] >= at) return true;
continue;
}
if (fire[k] <= at) continue;
seen[k] = true;
time[k] = at;
bq.push(k);
}
}
return false;
};
if (!canEscape(0)) return -1;
var hi = m * n;
if (canEscape(hi)) return BIG;
var lo = 0;
while (lo < hi) {
var mid = lo + Math.floor((hi - lo + 1) / 2);
if (canEscape(mid)) lo = mid; else hi = mid - 1;
}
return lo;
};Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.