Escape the Spreading Fire LeetCode solution in C++

1
class Solution {
2
 public:
3
  int maximumMinutes(vector<vector<int>> &grid) {
4
    int m = grid.size();
5
    int n = grid[0].size();
6
    vector<vector<int>> firetime(m, vector<int>(n, INT_MAX));
7
    queue<pair<int, int>> q;
8
    // push fire positions into queue, and set the time as 0
9
    for (int i = 0; i < m; i++) {
10
      for (int j = 0; j < n; j++) {
11
        if (grid[i][j] == 1) {
12
          q.push(make_pair(i, j));
13
          firetime[i][j] = 0;
14
        }
15
      }
16
    }
17
    int time = 0;
18
    pair<int, int> xy;
19
    int x, y;
20
    // use BFS to find fire spread time
21
    while (!q.empty()) {
22
      int points = q.size();
23
      time++;
24
      for (int i = 0; i < points; i++) {
25
        xy = q.front();
26
        q.pop();
27
        x = xy.first, y = xy.second;
28
        if (x - 1 >= 0 && grid[x - 1][y] == 0 && firetime[x - 1][y] == INT_MAX) {
29
          q.push(make_pair(x - 1, y));
30
          firetime[x - 1][y] = time;
31
        }
32
        if (x + 1 < m && grid[x + 1][y] == 0 && firetime[x + 1][y] == INT_MAX) {
33
          q.push(make_pair(x + 1, y));
34
          firetime[x + 1][y] = time;
35
        }
36
        if (y - 1 >= 0 && grid[x][y - 1] == 0 && firetime[x][y - 1] == INT_MAX) {
37
          q.push(make_pair(x, y - 1));
38
          firetime[x][y - 1] = time;
39
        }
40
        if (y + 1 < n && grid[x][y + 1] == 0 && firetime[x][y + 1] == INT_MAX) {
41
          q.push(make_pair(x, y + 1));
42
          firetime[x][y + 1] = time;
43
        }
44
      }
45
    }
46
    vector<vector<int>> peopletime(m, vector<int>(n, INT_MAX));
47
    time = 0;
48
    // push the initial position of the top left cell into the queue
49
    // and set the time as 0
50
    q.push(make_pair(0, 0));
51
    peopletime[0][0] = 0;
52
    // use BFS to find the traversal time
53
    while (!q.empty()) {
54
      int points = q.size();
55
      time++;
56
      for (int i = 0; i < points; i++) {
57
        xy = q.front();
58
        q.pop();
59
        x = xy.first, y = xy.second;
60
        if (x - 1 >= 0 && grid[x - 1][y] == 0 && peopletime[x - 1][y] == INT_MAX &&
61
            firetime[x - 1][y] > time) {
62
          q.push(make_pair(x - 1, y));
63
          peopletime[x - 1][y] = time;
64
        }
65
        if (x + 1 < m && grid[x + 1][y] == 0 && peopletime[x + 1][y] == INT_MAX &&
66
            firetime[x + 1][y] > time) {
67
          q.push(make_pair(x + 1, y));
68
          peopletime[x + 1][y] = time;
69
        }
70
        if (y - 1 >= 0 && grid[x][y - 1] == 0 && peopletime[x][y - 1] == INT_MAX &&
71
            firetime[x][y - 1] > time) {
72
          q.push(make_pair(x, y - 1));
73
          peopletime[x][y - 1] = time;
74
        }
75
        if (y + 1 < n && grid[x][y + 1] == 0 && peopletime[x][y + 1] == INT_MAX &&
76
            firetime[x][y + 1] > time) {
77
          q.push(make_pair(x, y + 1));
78
          peopletime[x][y + 1] = time;
79
        }
80
        if (((x == m - 2 && y == n - 1) || (x == m - 1 && y == n - 2)) &&
81
            (firetime[m - 1][n - 1] <= time)) {
82
          q.push(make_pair(m - 1, n - 1));
83
          peopletime[m - 1][n - 1] = time;
84
        }
85
      }
86
    }
87
    // if you cannot reach the safehouse or fire reaches the safehouse first,
88
    // return -1
89
    if (peopletime[m - 1][n - 1] == INT_MAX || firetime[m - 1][n - 1] < peopletime[m - 1][n - 1]) {
90
      return -1;
91
    }
92
    // if fire can never reach the safehouse,
93
    // return 1000000000
94
    if (firetime[m - 1][n - 1] == INT_MAX) {
95
      return 1000000000;
96
    }
97
    if (firetime[m - 1][n - 1] == peopletime[m - 1][n - 1]) {
98
      return 0;
99
    }
100
    int diff = (firetime[m - 1][n - 1] - peopletime[m - 1][n - 1]);
101
    if (m > 1 && n > 1) {
102
      if (peopletime[m - 2][n - 1] != INT_MAX && peopletime[m - 1][n - 2] != INT_MAX &&
103
          ((firetime[m - 2][n - 1] - peopletime[m - 2][n - 1]) > diff ||
104
           (firetime[m - 1][n - 2] - peopletime[m - 1][n - 2] > diff))) {
105
        return diff;
106
      }
107
    }
108
    return diff - 1;
109
  }
110
};