Leetcode Problem 2258. Escape the Spreading Fire

2258. Escape the Spreading Fire

Leetcode Solutions

BFS + Binary Search

  1. Run BFS from each fire cell to calculate the time it takes for the fire to reach every other cell. Store these times in a 2D array called fireTime.
  2. Initialize a binary search on the range of minutes you can stay at the initial position (0 to a large number like 10^9).
  3. For each iteration of the binary search, simulate the movement of the person using BFS, considering the number of minutes stayed initially and the fireTime array to avoid cells that will be on fire.
  4. If the person can reach the safehouse, update the binary search range to explore a higher number of minutes.
  5. If the person cannot reach the safehouse, update the binary search range to explore a lower number of minutes.
  6. Continue the binary search until the range is narrowed down to the maximum number of minutes that allow safe passage to the safehouse.
UML Thumbnail

Two Separate BFS for Fire and Person

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...