Latest Flooding Day with a Land Crossing

### Problem A `row` by `col` grid is entirely land on day 0. On each subsequent day, the next coordinate in `cells` becomes water; coordinates are one-based and each grid cell appears exactly once. Return the last day on which a path of land cells can connect any top-row cell to any bottom-row cell using only up, down, left and right moves. ```cpp class Solution { public: int latestDayToCross(int row, int col, vector<vector<int>>& cells); }; ``` ### Examples **Example 1:** ```text row = 2, col = 2, cells = [[2,2],[1,2],[2,1],[1,1]] Output: 2 Explanation: The left column stays open through day 2; day 3 floods its bottom cell. ``` **Example 2:** ```text row = 2, col = 3, cells = [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3]] Output: 2 Explanation: After day 2 the third column crosses; day 3 leaves no top-row land. ``` ### Constraints - `2 <= row,col <= 2 * 10^4`; `4 <= row*col <= 2 * 10^4`. - `cells.length == row*col`; all coordinates are unique and within the grid. ### Clarifying Questions Day d includes the first d floods. Starting and ending columns are unrestricted, and diagonal moves are forbidden. ```hint Inspect the structure Once crossing becomes impossible, can later flooding make it possible again? ``` ### Reasoning checkpoints - Find the final feasible day with the stated flood timing and one-based coordinates. - Consider every permitted top-row start and bottom-row finish, without admitting diagonal moves. - Justify the reported boundary between feasible and infeasible crossing days. ### Optional extensions Can you improve the asymptotic running time for the same flood schedule?