message: Update escape-the-spreading-fire.cpp
diff: // bfs
  class Solution {
  +public:
  + int maximumMinutes(vector<vector<int>>& grid) {
  + static const vector<pair<int, int>> directions{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
  + enum State {GRASS, FIRE, WALL, PERSON};
  + const int INF = 1e9;
  + const auto& bfs = [&]() {
  + unordered_map<int, unordered_map<int, unordered_map<int, int>>> time;
  + vector<tuple<int, int, int>> q;
  + for (int r = 0; r < size(grid); ++r) {
  + for (int c = 0; c < size(grid[0]); ++c) {
  + if (grid[r][c] == FIRE) {
  + q.emplace_back(r, c, FIRE);
  + }
  + }
  + }
  + q.emplace_back(0, 0, PERSON);
  + for (int d = 0; !empty(q); ++d) {
  + vector<tuple<int, int, int>> new_q;
  + for (const auto& [r, c, t] : q) {
  + for (const auto& [dr, dc] : directions) {
  + const int nr = r + dr, nc = c + dc;
  + if (!(0 <= nr && nr < size(grid) && 0 <= nc && nc < size(grid[0]) &&
  + grid[nr][nc] != WALL &&
  + ((t == FIRE && grid[nr][nc] != FIRE) ||
  + (t == PERSON && (grid[nr][nc] == GRASS ||
  + (grid[nr][nc] == FIRE && nr == size(grid) - 1 && nc == size(grid[0]) - 1 && d + 1 == time[FIRE][nr][nc])))))) {
  + continue;
  + }
  + if (grid[nr][nc] != FIRE) {
  + grid[nr][nc] = t;
  + }
  + if ((nr == size(grid) - 1 && nc == size(grid[0]) - 1) ||
  + (nr == size(grid) - 1 && nc == size(grid[0]) - 2) ||
  + (nr == size(grid) - 2 && nc == size(grid[0]) - 1)) {
  + time[t][nr][nc] = d + 1;
  + }
  + new_q.emplace_back(nr, nc, t);
  + }
  + }
  + q = move(new_q);
  + }
  + return time;
  + };
  + auto time = bfs();
  + if (!time[PERSON][size(grid) - 1][size(grid[0]) - 1]) {
  + return -1;
  + }
  + if (!time[FIRE][size(grid) - 1][size(grid[0]) - 1]) {
  + return INF;
  + }
  + const int diff = time[FIRE][size(grid) - 1][size(grid[0]) - 1] - time[PERSON][size(grid) - 1][size(grid[0]) - 1];
  + return (time[FIRE][size(grid) - 1][size(grid[0]) - 2] - time[PERSON][size(grid) - 1][size(grid[0]) - 2] == diff + 2 ||
  + time[FIRE][size(grid) - 2][size(grid[0]) - 1] - time[PERSON][size(grid) - 2][size(grid[0]) - 1] == diff + 2)
  + ? diff
  + : diff - 1;
  + }
  +};
  +
  +
  +// Time: O(m * n)
  +// Space: O(m * n)
  +// bfs
  +class Solution2 {
  public:
  int maximumMinutes(vector<vector<int>>& grid) {
  static const vector<pair<int, int>> directions{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
  