Escape the Spreading Fire – C++ Solution

Links to Other Language Solutions

Problem Description

Imagine you’re in a room, and suddenly, fire starts spreading like it’s auditioning for a role in a disaster movie. Your goal? Escape before the flames turn you into a crispy critter! The problem, aptly named “Escape the Spreading Fire,” presents a grid where each cell can either be a wall, a fire, or a safe space. Your mission, should you choose to accept it, is to determine the maximum number of minutes you can hang out in the grid before the fire catches up to you.

In simpler terms, you need to navigate through a grid while avoiding fire that spreads every minute. If you think this is just a game, think again! It’s a metaphor for life—sometimes you just need to run before the fire of responsibilities catches up with you!

Code Solution


class Solution {
 public:
  int maximumMinutes(vector>& grid) {
    const int kMax = grid.size() * grid[0].size();
    vector> fireMinute(grid.size(),
                                   vector(grid[0].size(), -1));
    buildFireGrid(grid, fireMinute);

    int ans = -1;
    int l = 0;
    int r = kMax;

    while (l <= r) {
      const int m = (l + r) / 2;
      if (canStayFor(grid, fireMinute, m)) {
        ans = m;
        l = m + 1;
      } else {
        r = m - 1;
      }
    }

    return ans == kMax ? 1'000'000'000 : ans;
  }

 private:
  static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  void buildFireGrid(const vector>& grid,
                     vector>& fireMinute) {
    queue> q;

    for (int i = 0; i < grid.size(); ++i)
      for (int j = 0; j < grid[0].size(); ++j)
        if (grid[i][j] == 1) {  // the fire
          q.emplace(i, j);
          fireMinute[i][j] = 0;
        }

    for (int minuteFromFire = 1; !q.empty(); ++minuteFromFire)
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [i, j] = q.front();
        q.pop();
        for (const auto& [dx, dy] : dirs) {
          const int x = i + dx;
          const int y = j + dy;
          if (x < 0 || x == grid.size() || y < 0 || y == grid[0].size())
            continue;
          if (grid[x][y] == 2)  // the wall
            continue;
          if (fireMinute[x][y] != -1)
            continue;
          fireMinute[x][y] = minuteFromFire;
          q.emplace(x, y);
        }
      }
  }

  bool canStayFor(const vector>& grid,
                  const vector>& fireMinute, int minute) {
    queue> q{{{0, 0}}};  // the start position
    vector> seen(grid.size(), vector(grid[0].size()));
    seen[0][0] = true;

    while (!q.empty()) {
      ++minute;
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [i, j] = q.front();
        q.pop();
        for (const auto& [dx, dy] : dirs) {
          const int x = i + dx;
          const int y = j + dy;
          if (x < 0 || x == grid.size() || y < 0 || y == grid[0].size())
            continue;
          if (grid[x][y] == 2)  // the wall
            continue;
          if (x == grid.size() - 1 && y == grid[0].size() - 1) {
            if (fireMinute[x][y] != -1 && fireMinute[x][y] < minute)
              continue;
            return true;
          }
          if (fireMinute[x][y] != -1 && fireMinute[x][y] <= minute)
            continue;
          if (seen[x][y])
            continue;
          q.emplace(x, y);
          seen[x][y] = true;
        }
      }
    }

    return false;
  }
};

Approach Explanation

The solution employs a breadth-first search (BFS) strategy to simulate the spread of fire across the grid. It first builds a grid that tracks how many minutes it takes for the fire to reach each cell. Then, using binary search, it determines the maximum time you can safely stay in the grid before the fire catches up. The algorithm checks if you can reach the exit (bottom-right corner) without being overtaken by the fire.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N * M * log(N * M))
Space Complexity	O(N * M)

Real-World Example

Think of a crowded movie theater where the fire alarm goes off. You need to find the quickest exit while avoiding the flames that are spreading through the aisles. Just like in the grid, you have to navigate through the seats (walls) and find the safest route to the exit before the fire catches up to you.