#2258

Escape the Spreading Fire

master · 1770 · lc hard +32 · verified · 37.7% accepted · 876 likes · top 16%

⚑ Multi-Source BFS

Description

You are given a 0-indexed 2D integer array grid of size m x n where:

 - 0 represents open grass,

 - 1 represents fire,

 - 2 represents an impassable wall.

You begin at (0, 0) and must reach the safehouse at (m - 1, n - 1). Each minute you step to an adjacent grass cell, then every fire spreads to its non-wall neighbors.

Return the maximum number of minutes you may wait at the start before moving and still safely reach the safehouse. Return -1 if safe arrival is impossible. Return 109 if you can always escape regardless of wait time.

Arriving at the safehouse on the same minute as the fire reaches it still counts as safe.

Adjacent cells share a side.

Example 1:

Input: grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]
Output: 3
Explanation: The figure above shows the scenario where you stay in the initial position for 3 minutes.
You will still be able to safely reach the safehouse.
Staying for more than 3 minutes will not allow you to safely reach the safehouse.

Example 2:

Input: grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]
Output: -1
Explanation: The figure above shows the scenario where you immediately move towards the safehouse.
Fire will spread to any cell you move towards and it is impossible to safely reach the safehouse.
Thus, -1 is returned.

Example 3:

Input: grid = [[0,0,0],[2,2,0],[1,2,0]]
Output: 1000000000
Explanation: The figure above shows the initial grid.
Notice that the fire is contained by walls and you will always be able to safely reach the safehouse.
Thus, 109 is returned.

Code

1
2
3