#1970
Last Day Where You Can Still Cross
expert · 1010 · lc hard +32 · premium · verified · 68.7% accepted · 2,376 likes · top 76%
Description
A 1-based binary matrix of size row by col starts entirely as land (0). Each day, one cell floods (becomes 1), specified by the 1-based 2D array cells where cells[i] = [ri, ci] indicates the cell that floods on day i.
Find the latest day on which you can still walk from any land cell in the top row to any land cell in the bottom row, moving only left, right, up, or down through land cells. Return that day number.
Example 1:
Input: row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
Output: 2
Explanation: The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 2.
Example 2:
Input: row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
Output: 1
Explanation: The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 1.
Example 3:
Input: row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
Output: 3
Explanation: The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 3.
Code
1
2
3