Escape the Spreading Fire
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].length2 <= m, n <= 300and4 <= m * n <= 2 * 10^4grid[i][j]is0(grass),1(fire) or2(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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every waiting time) | O((m · n)²) | O(m · n) |
| Binary search on the waiting time | O(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)
O((m · n)²)Up to m · n + 1 waiting times, each checked with an O(m · n) BFS.O(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.
- Multi-source BFS from all fire cells gives
fire[r][c](infinity if never burned). check(w): you are at the start at minutew(fail iffire[0][0] <= w). BFS; a grass cell may be entered at minutetiffire > t, the safehouse iffire >= t.- For
wfrom 0 tom · n: the first failingwgives answerw - 1. If none fails, return10^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;
}
}class Solution:
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def fireTimes(self, grid: List[List[int]]) -> List[List[float]]:
m, n = len(grid), len(grid[0])
fire = [[inf] * 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:
i, j = q.popleft()
for di, dj in self.DIRS:
r, k = i + di, j + dj
if 0 <= r < m and 0 <= k < n and grid[r][k] == 0 and fire[r][k] == inf:
fire[r][k] = fire[i][j] + 1
q.append((r, k))
return fire
def canEscape(self, grid: List[List[int]], fire: List[List[float]], w: int) -> bool:
m, n = len(grid), len(grid[0])
if fire[0][0] <= w:
return False
time = [[-1] * n for _ in range(m)]
time[0][0] = w
q = deque([(0, 0)])
while q:
i, j = q.popleft()
t = time[i][j] + 1
for di, dj in self.DIRS:
r, k = i + di, j + dj
if not (0 <= r < m and 0 <= k < n) or grid[r][k] != 0 or time[r][k] != -1:
continue
if r == m - 1 and k == n - 1:
if fire[r][k] >= t:
return True
continue
if fire[r][k] <= t:
continue
time[r][k] = t
q.append((r, k))
return False
def maximumMinutes(self, grid: List[List[int]]) -> int:
fire = self.fireTimes(grid)
limit = len(grid) * len(grid[0])
for w in range(limit + 1):
if not self.canEscape(grid, fire, w):
return w - 1
return 1000000000class Solution {
const int INF = INT_MAX;
int DIRS[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
vector<vector<int>> fireTimes(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> fire(m, vector<int>(n, INF));
queue<pair<int, int>> q;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) {
fire[i][j] = 0;
q.push({i, j});
}
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
for (auto& d : DIRS) {
int r = i + d[0], k = j + d[1];
if (r < 0 || k < 0 || r >= m || k >= n || grid[r][k] != 0 || fire[r][k] != INF) continue;
fire[r][k] = fire[i][j] + 1;
q.push({r, k});
}
}
return fire;
}
bool canEscape(vector<vector<int>>& grid, vector<vector<int>>& fire, int w) {
int m = grid.size(), n = grid[0].size();
if (fire[0][0] <= w) return false;
vector<vector<int>> time(m, vector<int>(n, -1));
time[0][0] = w;
queue<pair<int, int>> q;
q.push({0, 0});
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
int t = time[i][j] + 1;
for (auto& d : DIRS) {
int r = i + d[0], k = j + 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.push({r, k});
}
}
return false;
}
public:
int maximumMinutes(vector<vector<int>>& grid) {
vector<vector<int>> fire = fireTimes(grid);
int limit = grid.size() * grid[0].size();
for (int w = 0; w <= limit; w++) {
if (!canEscape(grid, fire, w)) return w - 1;
}
return 1000000000;
}
};function maximumMinutes(grid) {
const m = grid.length, n = grid[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const fire = Array.from({ length: m }, () => new Array(n).fill(Infinity));
let q = [];
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (grid[i][j] === 1) {
fire[i][j] = 0;
q.push([i, j]);
}
for (let h = 0; h < q.length; h++) {
const [i, j] = q[h];
for (const [di, dj] of DIRS) {
const r = i + di, k = j + dj;
if (r < 0 || k < 0 || r >= m || k >= n || grid[r][k] !== 0 || fire[r][k] !== Infinity) continue;
fire[r][k] = fire[i][j] + 1;
q.push([r, k]);
}
}
const canEscape = (w) => {
if (fire[0][0] <= w) return false;
const time = Array.from({ length: m }, () => new Array(n).fill(-1));
time[0][0] = w;
const bq = [[0, 0]];
for (let h = 0; h < bq.length; h++) {
const [i, j] = bq[h];
const t = time[i][j] + 1;
for (const [di, dj] of DIRS) {
const r = i + di, k = j + dj;
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;
bq.push([r, k]);
}
}
return false;
};
const limit = m * n;
for (let w = 0; w <= limit; w++) {
if (!canEscape(w)) return w - 1;
}
return 1000000000;
}2Binary search on the waiting time
O(m · n · log(m · n))About log(m · n) checks, each an O(m · n) BFS.O(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.
- Compute fire times with a multi-source BFS.
- If
check(0)fails, return -1. Ifcheck(m · n)succeeds, return10^9. - Binary search the largest
wwithcheck(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;
}
}class Solution:
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def fireTimes(self, grid: List[List[int]]) -> List[List[float]]:
m, n = len(grid), len(grid[0])
fire = [[inf] * 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:
i, j = q.popleft()
for di, dj in self.DIRS:
r, k = i + di, j + dj
if 0 <= r < m and 0 <= k < n and grid[r][k] == 0 and fire[r][k] == inf:
fire[r][k] = fire[i][j] + 1
q.append((r, k))
return fire
def canEscape(self, grid: List[List[int]], fire: List[List[float]], w: int) -> bool:
m, n = len(grid), len(grid[0])
if fire[0][0] <= w:
return False
time = [[-1] * n for _ in range(m)]
time[0][0] = w
q = deque([(0, 0)])
while q:
i, j = q.popleft()
t = time[i][j] + 1
for di, dj in self.DIRS:
r, k = i + di, j + dj
if not (0 <= r < m and 0 <= k < n) or grid[r][k] != 0 or time[r][k] != -1:
continue
if r == m - 1 and k == n - 1:
if fire[r][k] >= t:
return True
continue
if fire[r][k] <= t:
continue
time[r][k] = t
q.append((r, k))
return False
def maximumMinutes(self, grid: List[List[int]]) -> int:
fire = self.fireTimes(grid)
limit = len(grid) * len(grid[0])
if not self.canEscape(grid, fire, 0):
return -1
if self.canEscape(grid, fire, limit):
return 1000000000
lo, hi = 0, limit - 1
while lo < hi:
mid = lo + (hi - lo + 1) // 2
if self.canEscape(grid, fire, mid):
lo = mid
else:
hi = mid - 1
return loclass Solution {
const int INF = INT_MAX;
int DIRS[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
vector<vector<int>> fireTimes(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> fire(m, vector<int>(n, INF));
queue<pair<int, int>> q;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) {
fire[i][j] = 0;
q.push({i, j});
}
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
for (auto& d : DIRS) {
int r = i + d[0], k = j + d[1];
if (r < 0 || k < 0 || r >= m || k >= n || grid[r][k] != 0 || fire[r][k] != INF) continue;
fire[r][k] = fire[i][j] + 1;
q.push({r, k});
}
}
return fire;
}
bool canEscape(vector<vector<int>>& grid, vector<vector<int>>& fire, int w) {
int m = grid.size(), n = grid[0].size();
if (fire[0][0] <= w) return false;
vector<vector<int>> time(m, vector<int>(n, -1));
time[0][0] = w;
queue<pair<int, int>> q;
q.push({0, 0});
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
int t = time[i][j] + 1;
for (auto& d : DIRS) {
int r = i + d[0], k = j + 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.push({r, k});
}
}
return false;
}
public:
int maximumMinutes(vector<vector<int>>& grid) {
vector<vector<int>> fire = fireTimes(grid);
int limit = grid.size() * grid[0].size();
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;
}
};function maximumMinutes(grid) {
const m = grid.length, n = grid[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const fire = Array.from({ length: m }, () => new Array(n).fill(Infinity));
const q = [];
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (grid[i][j] === 1) {
fire[i][j] = 0;
q.push([i, j]);
}
for (let h = 0; h < q.length; h++) {
const [i, j] = q[h];
for (const [di, dj] of DIRS) {
const r = i + di, k = j + dj;
if (r < 0 || k < 0 || r >= m || k >= n || grid[r][k] !== 0 || fire[r][k] !== Infinity) continue;
fire[r][k] = fire[i][j] + 1;
q.push([r, k]);
}
}
const canEscape = (w) => {
if (fire[0][0] <= w) return false;
const time = Array.from({ length: m }, () => new Array(n).fill(-1));
time[0][0] = w;
const bq = [[0, 0]];
for (let h = 0; h < bq.length; h++) {
const [i, j] = bq[h];
const t = time[i][j] + 1;
for (const [di, dj] of DIRS) {
const r = i + di, k = j + dj;
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;
bq.push([r, k]);
}
}
return false;
};
const limit = m * n;
if (!canEscape(0)) return -1;
if (canEscape(limit)) return 1000000000;
let lo = 0, hi = limit - 1;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo + 1) / 2);
if (canEscape(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}3Optimal (two BFS and compare arrival times)
O(m · n)Two BFS passes over the grid, then O(1) work.O(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.
- BFS from all fire cells gives
fire; BFS from(0, 0)over grass givesyou(infinity if unreachable). - If
you[safe]is infinite, return -1. Iffire[safe]is infinite, return10^9. d = fire[safe] - you[safe]; ifd < 0, return -1.- 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, returnd; otherwise returnd - 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;
}
}class Solution:
def maximumMinutes(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
def bfs(sources: List[Tuple[int, int]]) -> List[List[float]]:
dist = [[inf] * n for _ in range(m)]
q = deque()
for i, j in sources:
dist[i][j] = 0
q.append((i, j))
while q:
i, j = q.popleft()
for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
r, k = i + di, j + dj
if 0 <= r < m and 0 <= k < n and grid[r][k] == 0 and dist[r][k] == inf:
dist[r][k] = dist[i][j] + 1
q.append((r, k))
return dist
fire = bfs([(i, j) for i in range(m) for j in range(n) if grid[i][j] == 1])
you = bfs([(0, 0)])
if you[m - 1][n - 1] == inf:
return -1
if fire[m - 1][n - 1] == inf:
return 1000000000
d = fire[m - 1][n - 1] - you[m - 1][n - 1]
if d < 0:
return -1
def slack(r: int, c: int) -> float:
if you[r][c] == inf:
return -inf
return fire[r][c] - you[r][c]
if slack(m - 2, n - 1) > d or slack(m - 1, n - 2) > d:
return d
return d - 1class Solution {
const int INF = INT_MAX;
vector<vector<int>> bfs(vector<vector<int>>& grid, vector<pair<int, int>>& sources) {
int m = grid.size(), n = grid[0].size();
int DIRS[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
vector<vector<int>> dist(m, vector<int>(n, INF));
queue<pair<int, int>> q;
for (auto& s : sources) {
dist[s.first][s.second] = 0;
q.push(s);
}
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
for (auto& d : DIRS) {
int r = i + d[0], k = j + d[1];
if (r < 0 || k < 0 || r >= m || k >= n || grid[r][k] != 0 || dist[r][k] != INF) continue;
dist[r][k] = dist[i][j] + 1;
q.push({r, k});
}
}
return dist;
}
long long slack(vector<vector<int>>& fire, vector<vector<int>>& you, int r, int c) {
if (you[r][c] == INF) return LLONG_MIN;
if (fire[r][c] == INF) return LLONG_MAX;
return (long long)fire[r][c] - you[r][c];
}
public:
int maximumMinutes(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<pair<int, int>> fires, start = {{0, 0}};
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) fires.push_back({i, j});
vector<vector<int>> fire = bfs(grid, fires);
vector<vector<int>> you = bfs(grid, start);
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;
}
};function maximumMinutes(grid) {
const m = grid.length, n = grid[0].length;
const bfs = (sources) => {
const dist = Array.from({ length: m }, () => new Array(n).fill(Infinity));
const q = [];
for (const [i, j] of sources) {
dist[i][j] = 0;
q.push([i, j]);
}
for (let h = 0; h < q.length; h++) {
const [i, j] = q[h];
for (const [di, dj] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const r = i + di, k = j + dj;
if (r < 0 || k < 0 || r >= m || k >= n || grid[r][k] !== 0 || dist[r][k] !== Infinity) continue;
dist[r][k] = dist[i][j] + 1;
q.push([r, k]);
}
}
return dist;
};
const fires = [];
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (grid[i][j] === 1) fires.push([i, j]);
const fire = bfs(fires);
const you = bfs([[0, 0]]);
if (you[m - 1][n - 1] === Infinity) return -1;
if (fire[m - 1][n - 1] === Infinity) return 1000000000;
const d = fire[m - 1][n - 1] - you[m - 1][n - 1];
if (d < 0) return -1;
const slack = (r, c) => (you[r][c] === Infinity ? -Infinity : fire[r][c] - you[r][c]);
if (slack(m - 2, n - 1) > d || slack(m - 1, n - 2) > d) return d;
return d - 1;
}Edge cases to test
- No fire at all: the answer is
10^9as long as the safehouse is reachable - The safehouse is walled off:
-1regardless 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.