How Long Can You Wait Before the Fire Arrives
Solve this ProblemA factory floor plan has open floor, solid walls and burning machines. Every minute the flames spread to all neighbouring open cells. A worker at the top-left corner has to get to the emergency exit at the bottom-right corner, stepping one cell per minute, and may stand still for a while first. What is the longest the worker can wait and still make it out alive?
Two ideas make it manageable: a breadth-first search from the fire tells the minute at which each cell burns, and since waiting longer never helps, the longest safe waiting time can be found with a binary search, testing each candidate with a second breadth-first search that compares your arrival minute with the fire's.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ rows·cols; 1 ≤ rows, cols ≤ 6; grid[r][c] is 0 (open floor), 1 (solid wall) or 2 (burning machine); the top-left and the bottom-right cell are open floor - ◆
A worker starts on the top-left cell and must reach the emergency exit on the bottom-right cell. Each minute the worker steps to a side-neighbouring cell that is not a wall; after the step, the flames spread from every burning cell to all its side-neighbouring open cells (walls stop them) - ◆
The worker may stand still at the start for some minutes before setting off. Being on a cell at the moment the flames enter it is fatal, except that reaching the exit in the very minute the flames arrive there is fine - ◆
Return the most minutes the worker can stand still and still reach the exit safely; -1 if escape is impossible even without waiting; 999999 if no amount of waiting can ever be too long
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Simulate Every Waiting Time Minute by Minute
BruteFor each waiting time w = 0, 1, 2, … simulate the whole story: let the fire spread for w minutes (the fire spreading layer by layer), check that the start has not caught fire, and then advance both sides minute by minute: the person's frontier moves to all reachable unburnt neighbours (returning success if one is the shelter), the fire spreads one step, and every frontier cell that has just caught fire is dropped. Waiting can only make things worse, so the answer is the last w that works: -1 if even w = 0 fails, and 999999 if a very long wait (R·C minutes, longer than the fire needs to burn everything it can) still works.
O(W · (W + steps) · R·C)O(R·C)1class Solution {
2 private void spread(int[][] grid, boolean[][] burning) {
3 int rows = grid.length, cols = grid[0].length;
4 int[] dr = {1, -1, 0, 0};
5 int[] dc = {0, 0, 1, -1};
6 boolean[][] fresh = new boolean[rows][cols];
7 for (int r = 0; r < rows; r++) {
8 for (int c = 0; c < cols; c++) {
9 if (!burning[r][c]) continue;
10 for (int d = 0; d < 4; d++) {
11 int nr = r + dr[d], nc = c + dc[d];
12 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] != 1) fresh[nr][nc] = true;
13 }
14 }
15 }
16 for (int r = 0; r < rows; r++) {
17 for (int c = 0; c < cols; c++) {
18 if (fresh[r][c]) burning[r][c] = true;
19 }
20 }
21 }
22
23 private boolean survives(int[][] grid, int wait) {
24 int rows = grid.length, cols = grid[0].length;
25 int[] dr = {1, -1, 0, 0};
26 int[] dc = {0, 0, 1, -1};
27 boolean[][] burning = new boolean[rows][cols];
28 for (int r = 0; r < rows; r++) {
29 for (int c = 0; c < cols; c++) burning[r][c] = grid[r][c] == 2;
30 }
31 for (int minute = 0; minute < wait; minute++) spread(grid, burning);
32 if (burning[0][0]) return false;
33 boolean[][] visited = new boolean[rows][cols];
34 List<int[]> frontier = new ArrayList<>();
35 visited[0][0] = true;
36 frontier.add(new int[]{0, 0});
37 while (!frontier.isEmpty()) {
38 List<int[]> next = new ArrayList<>();
39 for (int[] cell : frontier) {
40 for (int d = 0; d < 4; d++) {
41 int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
42 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
43 if (grid[nr][nc] == 1 || visited[nr][nc] || burning[nr][nc]) continue;
44 if (nr == rows - 1 && nc == cols - 1) return true;
45 visited[nr][nc] = true;
46 next.add(new int[]{nr, nc});
47 }
48 }
49 spread(grid, burning);
50 frontier = new ArrayList<>();
51 for (int[] cell : next) {
52 if (!burning[cell[0]][cell[1]]) frontier.add(cell);
53 }
54 }
55 return false;
56 }
57
58 public int longestWait(int[][] grid) {
59 int limit = grid.length * grid[0].length;
60 if (!survives(grid, 0)) return -1;
61 if (survives(grid, limit)) return 999999;
62 int best = 0;
63 for (int wait = 1; wait <= limit; wait++) {
64 if (survives(grid, wait)) best = wait;
65 else break;
66 }
67 return best;
68 }
69}Optimal — Fire Arrival Times, Then Binary Search on the Waiting Time
OptimalRun one multi-source breadth-first search from all burning cells to get the minute fireTime[r][c] at which every cell catches fire (infinity if never). For a fixed waiting time w, a breadth-first search for the person decides whether escape is possible: the start needs fireTime > w, every other cell you enter at minute t needs t < fireTime (you must arrive strictly before the fire), and for the shelter t ≤ fireTime is enough. If waiting w minutes works, waiting less also works, so binary search the largest w (between 0 and R·C). If w = 0 fails return -1; if w = R·C works the fire can never catch you: return 999999.
O(R·C · log(R·C))O(R·C)1class Solution {
2 private boolean canEscape(int[][] grid, int[][] fireTime, int wait) {
3 int rows = grid.length, cols = grid[0].length;
4 if (fireTime[0][0] <= wait) return false;
5 int[] dr = {1, -1, 0, 0};
6 int[] dc = {0, 0, 1, -1};
7 int[][] arrive = new int[rows][cols];
8 for (int[] row : arrive) Arrays.fill(row, -1);
9 arrive[0][0] = wait;
10 Deque<int[]> queue = new ArrayDeque<>();
11 queue.add(new int[]{0, 0});
12 while (!queue.isEmpty()) {
13 int[] cell = queue.poll();
14 for (int d = 0; d < 4; d++) {
15 int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
16 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
17 if (grid[nr][nc] != 0 || arrive[nr][nc] != -1) continue;
18 int time = arrive[cell[0]][cell[1]] + 1;
19 boolean last = nr == rows - 1 && nc == cols - 1;
20 if (last ? time <= fireTime[nr][nc] : time < fireTime[nr][nc]) {
21 arrive[nr][nc] = time;
22 queue.add(new int[]{nr, nc});
23 }
24 }
25 }
26 return arrive[rows - 1][cols - 1] != -1;
27 }
28
29 public int longestWait(int[][] grid) {
30 int rows = grid.length, cols = grid[0].length;
31 int INF = 1_000_000;
32 int[] dr = {1, -1, 0, 0};
33 int[] dc = {0, 0, 1, -1};
34 int[][] fireTime = new int[rows][cols];
35 Deque<int[]> queue = new ArrayDeque<>();
36 for (int r = 0; r < rows; r++) {
37 for (int c = 0; c < cols; c++) {
38 if (grid[r][c] == 2) {
39 fireTime[r][c] = 0;
40 queue.add(new int[]{r, c});
41 } else {
42 fireTime[r][c] = INF;
43 }
44 }
45 }
46 while (!queue.isEmpty()) {
47 int[] cell = queue.poll();
48 for (int d = 0; d < 4; d++) {
49 int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
50 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 0 && fireTime[nr][nc] == INF) {
51 fireTime[nr][nc] = fireTime[cell[0]][cell[1]] + 1;
52 queue.add(new int[]{nr, nc});
53 }
54 }
55 }
56 int limit = rows * cols;
57 if (!canEscape(grid, fireTime, 0)) return -1;
58 if (canEscape(grid, fireTime, limit)) return 999999;
59 int lo = 0, hi = limit;
60 while (lo < hi) {
61 int mid = (lo + hi + 1) / 2;
62 if (canEscape(grid, fireTime, mid)) {
63 lo = mid;
64 } else {
65 hi = mid - 1;
66 }
67 }
68 return lo;
69 }
70}