How Long Can You Wait Before the Fire

Hard

The field is an m × n matrix field. Every cell holds one of three values: - 0: grass, - 1: fire, - 2: a wall that neither you nor the fire can pass. You start in the top-left cell (0, 0), and the shelter is the bottom-right cell (m - 1, n - 1). Each minute you may step onto a grass cell that shares a side with yours. Right after your move, every burning cell sets fire to all cells sharing a side with it, except walls. Return the largest number of minutes you can stand at the start and still reach the shelter safely. If you cannot reach it even without waiting, return -1. If you can reach it no matter how long you wait, return 10⁹. If the fire reaches the shelter in the same minute you step into it, you still made it.

Example 1

field=[[0, 0, 0, 1], [0, 2, 2, 2], [0, 0, 0, 0]] → 2

The fire moves left along the top row and reaches the start after 3 minutes, then chases you down the left column. If you wait 2 minutes, you stay one step ahead of it for all 5 steps to the shelter. After 3 minutes of waiting the start is already burning.

Example 2

field=[[0, 0, 0, 0], [2, 2, 2, 0], [1, 2, 0, 0]] → 1000000000

The fire is walled in at the bottom-left corner and never spreads, so you can wait as long as you like: the answer is 10⁹.

Example 3

field=[[0, 0, 0, 0, 0], [0, 2, 2, 2, 0], [0, 2, 1, 0, 0]] → -1

The fire reaches the shelter in 2 minutes, while any path to it takes 6 steps. You cannot make it even without waiting, so the answer is -1.

Constraints

m == len(field), n == len(field[i])
2 ≤ m, n ≤ 300
4 ≤ m · n ≤ 2 · 10⁴
field[i][j] is 0, 1 or 2
field[0][0] == field[m - 1][n - 1] == 0

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Array Binary Search Matrix