Show problems as
Classic problem #2258HardArrayBinary SearchBreadth-First SearchMatrix

Escape the Spreading Fire

Real-world version: Waiting Out the Creeping Slurry
Tracked in this browser only
Read Escape the Spreading Fire on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A quarry floor is laid out as m rows of n panels. panels[i][j] reads 0 for a firm panel, 1 for a panel already under slurry, and 2 for a pillar. You stand on the ramp at panels[0][0] and want to reach the shed at panels[m - 1][n - 1], and both of those are firm.

Time passes in whole minutes, and each minute of the walk holds two things in this order:

  1. you step onto a panel sharing a side with the one you are on, and it must be firm and not yet under slurry;
  2. the slurry then creeps onto every firm panel sharing a side with a panel already under it.

Pillars stop the slurry just as they stop you. If the slurry creeps onto the panel you are standing on, it has you. Stepping onto the shed ends the walk, so slurry creeping onto the shed during that same minute does not.

Before setting off you may linger on the ramp for a whole number of minutes, and the slurry creeps during every one of them. Once you set off you step every minute until you are on the shed.

Return the largest number of minutes you can linger and still reach the shed. Return 10^9 if you can linger for any number of minutes whatsoever, and -1 if you cannot reach the shed even by setting off at once.

Examples

Example 1

Input
panels = [[0, 0, 0, 1], [0, 2, 2, 2], [0, 0, 0, 0], [0, 0, 0, 0]]
Output
2

The pillars leave one way down off the top row, so the walk to the shed is six steps and the slurry, starting at the far end of the top row, needs nine minutes to follow it there. Lingering three would land you on the shed as the slurry arrives, which is allowed, but it would also put the slurry on the panel before the shed while you were still standing on it. Lingering two keeps you a minute clear the whole way.

Example 2

Input
panels = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output
-1

The slurry sits one panel from the shed and covers it after two minutes, while the shortest way around the wet middle panel takes four steps. The slurry is there first even if you leave at once.

Example 3

Input
panels = [[0, 0, 0, 0, 0], [0, 0, 2, 0, 0], [0, 2, 1, 2, 0], [0, 0, 2, 0, 0], [0, 0, 0, 0, 0]]
Output
1000000000

Pillars hem the one wet panel in on all four sides, so the slurry never moves. Nothing on the way to the shed is ever wet, so the lingering has no ceiling.

Constraints

  • m == panels.length
  • n == panels[i].length
  • 2 <= panels.length <= 300
  • 2 <= panels[i].length <= 300
  • 4 <= m * n <= 2 * 10^4
  • 0 <= panels[i][j] <= 2
  • panels[0][0] == panels[m - 1][n - 1] == 0

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def maximum_minutes(panels: list[list[int]]) -> int:
Java
public int maximumMinutes(int[][] panels)

More on the same topics