How Long Can You Wait Before the Fire Arrives
Implement longestWait
A factory floor plan has open floor, solid walls and burning machines. Every minute the flames spread to all neighbouring open cells. A worker at the top-left corner has to get to the emergency exit at the bottom-right corner, stepping one cell per minute, and may stand still for a while first. What is the longest the worker can wait and still make it out alive?
Two ideas make it manageable: a breadth-first search from the fire tells the minute at which each cell burns, and since waiting longer never helps, the longest safe waiting time can be found with a binary search, testing each candidate with a second breadth-first search that compares your arrival minute with the fire's.
Example 1:
Input: grid = [[0,0,0,0],[0,1,1,2],[0,0,0,1],[0,0,0,0]]
Output: 3
Example 2:
Input: grid = [[0,2],[1,0]]
Output: -1
Example 3:
Input: grid = [[0,0],[0,0]]
Output: 999999
+ 13 hidden test cases run on Submit.
Constraints:
- ●
2 ≤ rows·cols; 1 ≤ rows, cols ≤ 6; grid[r][c] is 0 (open floor), 1 (solid wall) or 2 (burning machine); the top-left and the bottom-right cell are open floor - ●
A worker starts on the top-left cell and must reach the emergency exit on the bottom-right cell. Each minute the worker steps to a side-neighbouring cell that is not a wall; after the step, the flames spread from every burning cell to all its side-neighbouring open cells (walls stop them) - ●
The worker may stand still at the start for some minutes before setting off. Being on a cell at the moment the flames enter it is fatal, except that reaching the exit in the very minute the flames arrive there is fine - ●
Return the most minutes the worker can stand still and still reach the exit safely; -1 if escape is impossible even without waiting; 999999 if no amount of waiting can ever be too long
grid =