793. The Last Day the Crossing Holds
A tidal flat is a grid of R rows and C columns. On day 0 every cell is dry land. On day
1 the first listed cell floods, on day 2 the second, and so on; every cell floods exactly once,
so R * C cells are listed and the flat is entirely under water after the last of them.
At the end of day k you may walk from ANY cell of the top row to ANY cell of the bottom row,
moving between cells that share a side and stepping only on cells that have not yet flooded.
Print the largest k for which that walk is still possible. Day 0 always qualifies, because
nothing has flooded yet.
2 x 2, floods (1,1) (2,1) (1,2) (2,2) -> 2
2 x 2, floods (1,1) (1,2) (2,1) (2,2) -> 1
In the first flat, after two days the cells (1,2) and (2,2) are still dry and sit one above
the other, so the second column carries the walk. In the second flat the whole top row is gone
after two days, so the answer drops to 1.
## Why replaying the days one at a time is too slow
Testing one day is one breadth first search over the dry cells, O(R * C). Replaying day 1, day
2, day 3 and so on costs R * C searches, which at 200 * 200 is 1.6 * 10^9 cell visits.
Note what does NOT work: adding cells back and using union-find, the way problem 987 does. That structure can merge two regions but it cannot split one, and here the flat is falling apart rather than coming together. Running the list BACKWARDS turns removals into additions and is a genuinely different accepted solution; binary search gets there without reversing anything.
## Why the predicate is monotone
Flooding never dries a cell. The set of dry cells on day k + 1 is a subset of the set on day
k, so any walk that survives to day k + 1 also existed on day k. The answers to "is the
crossing open at the end of day k?" read YES YES YES no no, and the answer is the LAST
YES.
## The bounds, and the direction of the search
lo = 0, which always works. hi = R * C, which never does, because by then every cell is under
water.
Because the answer is the last success rather than the first, success moves lo up to mid and
failure moves hi down to mid - 1. Round the midpoint UP, mid = hi - (hi - lo) / 2, or the
loop stalls when hi is lo + 1.
## The boundary that breaks a careless implementation
A one row grid. The top row and the bottom row are the same row, so the walk is a single cell and the answer is the day before that row loses every cell it has. A search that starts at the top row and only looks for a cell strictly below it never finds one.
Store, for each cell, the day it floods; then "dry at the end of day k" is the single
comparison floodDay > k. Rebuilding a set of flooded cells for every candidate is what turns an
elegant check into a slow one.
## Related problems
Problem 987 answers the mirror question, the first moment a graph becomes connected as edges are added. Problem 791 also searches a grid threshold, but there the grid never changes.
## Cost
Time O(R * C * log(R * C)). Space O(R * C).
Constraints - `1 ≤ R ≤ 200` - `1 ≤ C ≤ 200` - the `R * C` listed cells are every cell of the grid, each exactly once - `1 ≤ r ≤ R`, `1 ≤ c ≤ C`
Input
The first line contains two integers R and C.
Each of the next R * C lines contains two integers r and c, the 1-based row and column of the cell that floods on that day, in day order.
Output
Print one integer, the last day on which a walk from the top row to the bottom row over dry cells still exists. Print it alone on one line, with no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.