Escape the Spreading Fire LeetCode solution in Java

1
class Solution {
2
  public int maximumMinutes(int[][] grid) {
3
    int m = grid.length;
4
    int n = grid[0].length;
5

6
    int[][] times = new int[m][n];
7
    for (int[] row : times) {
8
      Arrays.fill(row, Integer.MAX_VALUE);
9
    }
10

11
    int[] dir = new int[] {-1, 0, 1, 0, -1};
12

13
    // Queue for running BFS
14
    Deque<int[]> fires = new ArrayDeque<>();
15

16
    for (int row = 0; row < m; row++) {
17
      for (int col = 0; col < n; col++) {
18
        if (grid[row][col] == 1) {
19
          times[row][col] = 0;
20
          fires.offer(new int[] {row, col});
21
        }
22
      }
23
    }
24

25
    int time = 1;
26
    while (!fires.isEmpty()) {
27
      int size = fires.size();
28

29
      for (int i = 0; i < size; i++) {
30
        int[] pos = fires.poll();
31

32
        for (int j = 0; j < 4; j++) {
33
          int x = pos[0] + dir[j];
34
          int y = pos[1] + dir[j + 1];
35

36
          if (x >= 0
37
              && y >= 0
38
              && x < m
39
              && y < n
40
              && grid[x][y] == 0
41
              && times[x][y] == Integer.MAX_VALUE) {
42
            times[x][y] = time;
43
            fires.offer(new int[] {x, y});
44
          }
45
        }
46
      }
47

48
      time++;
49
    }
50

51
    fires.clear();
52

53
    int ans = Integer.MAX_VALUE;
54
    fires.offer(new int[] {0, 0});
55
    grid[0][0] = 2;
56

57
    time = 1;
58
    while (!fires.isEmpty() && grid[m - 1][n - 1] == 0) {
59
      int size = fires.size();
60

61
      int t = Integer.MIN_VALUE;
62

63
      for (int i = 0; i < size && grid[m - 1][n - 1] == 0; i++) {
64
        int[] pos = fires.poll();
65

66
        for (int j = 0; j < 4 && grid[m - 1][n - 1] == 0; j++) {
67

68
          int x = pos[0] + dir[j];
69
          int y = pos[1] + dir[j + 1];
70

71
          if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y] == 0 && times[x][y] >= time) {
72
            if (x == m - 1 && y == n - 1) {
73
              t = times[x][y] - time;
74
              grid[x][y] = 2;
75
              break;
76
            }
77

78
            grid[x][y] = 2;
79
            fires.offer(new int[] {x, y});
80

81
            // if times[x][y] == Integer.MAX_VALUE, fire will never reach this cell and it will
82
            // contribute maximum wait time
83
            t = Math.max(t, times[x][y] == Integer.MAX_VALUE ? 1000000000 : times[x][y] - time - 1);
84
          }
85
        }
86
      }
87

88
      ans = Math.min(ans, t);
89

90
      time++;
91
    }
92

93
    // You can never reach the safe house
94
    if (grid[m - 1][n - 1] != 2) {
95
      return -1;
96
    }
97

98
    // you can reach the safe house but fire can not
99
    if (times[m - 1][n - 1] == Integer.MAX_VALUE) {
100
      return 1000000000;
101
    }
102

103
    return ans == Integer.MAX_VALUE || ans == Integer.MIN_VALUE ? -1 : ans;
104
  }
105
}