796. Minutes Before You Must Run
A field is a grid of R rows and C columns. Each cell is 0 for open ground, 1 for a
wall, or 2 for a cell that is already alight at minute 0. You stand on the top left cell and
the shelter is the bottom right cell; both are open ground.
Time runs in whole minutes.
- At the end of every minute the fire spreads from each burning cell to the open ground cells
- sharing a side with it. Walls never burn and never let fire through.
- You may stand still on the starting cell for
tminutes, then you move one cell per minute to - a side-sharing cell that is not a wall.
- You may be on a cell at minute
Tonly if the fire reaches that cell strictly afterT. The - one exception is the shelter: reaching it in the same minute the fire does still counts as
- escaping.
Print the largest t you may wait and still escape. Print -1 if you cannot escape even by
leaving at once, and print forever if no amount of waiting stops you.
0 0 0 0
0 1 0 0 -> 1
2 1 0 0
The fire starts at the bottom left. Waiting one minute still leaves a route up and across; waiting two does not.
## Two phases, and why the first one is not a binary search
Where the fire gets to, and when, does not depend on you at all. One breadth first search from
every burning cell at once gives fire[r][c], the minute the fire arrives, or infinity when it
never does. Compute that once and never again.
Only the second phase depends on t. Given t, walk outward from the start with a breadth first
search, arriving at a cell at minute t + (steps taken), and accept a cell only when that minute
is strictly before fire says the flames arrive, with the shelter allowed to tie. That is one
O(R * C) check per candidate.
## Why the predicate is monotone
Waiting longer never helps. The route that escapes after waiting t + 1 reaches every one of its
cells one minute later than it would after waiting t, and the fire arrives at the same minutes
either way, so the same route also escapes after waiting t. Feasible waits form a prefix
YES YES no no, and the answer is the last YES.
## The bounds, and how forever is decided without a special case
lo = 0. hi = R * C.
The top of that range decides forever on its own. Every fire arrival time is at most
R * C - 1 when it is finite, and so is every step count, so a cell accepted at
t = R * C must be one the fire never reaches at all. If the check passes there, it passes for
every larger t too, and the answer is unbounded.
## The boundary that breaks a careless implementation
The shelter tie. Every other cell demands a strict inequality and the shelter demands a loose one, so the shelter has to be tested before it is enqueued, not after. Enqueue it under the strict rule and escapes that should count are thrown away.
The second is a one by one field. The start IS the shelter, no step is ever taken, and the answer
is forever whenever that cell never catches fire.
## Related problems
Problem 793 also searches a time at which a grid stops working, and problem 791 searches a threshold on the same shape of grid.
## Cost
Time O(R * C * log(R * C)). Space O(R * C).
Constraints - `1 ≤ R ≤ 200` - `1 ≤ C ≤ 200` - each cell is `0`, `1` or `2` - the top left cell and the bottom right cell are both `0`
Input
The first line contains two integers R and C.
Each of the next R lines contains C integers, each 0 for open ground, 1 for a wall or 2 for a cell alight at minute 0.
Output
Print one line holding either the largest number of minutes you may wait, or -1 when no wait at all works, or the word forever when every wait works. Print nothing else on the line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.