给你一个下标从 1 开始的二进制矩阵，其中 0 表示陆地，1 表示水域。同时给你 row 和 col 分别表示矩阵中行和列的数目。
一开始在第 0 天，整个 矩阵都是 陆地 。但每一天都会有一块新陆地被 水 淹没变成水域。给你一个下标从 1 开始的二维数组 cells ，其中 cells[i] = [ri, ci] 表示在第 i 天，第 ri 行 ci 列（下标都是从 1 开始）的陆地会变成 水域 （也就是 0 变成 1 ）。
你想知道从矩阵最 上面 一行走到最 下面 一行，且只经过陆地格子的 最后一天 是哪一天。你可以从最上面一行的 任意 格子出发，到达最下面一行的 任意 格子。你只能沿着 四个 基本方向移动（也就是上下左右）。
请返回只经过陆地格子能从最 上面 一行走到最 下面 一行的 最后一天 。
示例 1：
输入：row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]] 输出：2 解释：上图描述了矩阵从第 0 天开始是如何变化的。 可以从最上面一行到最下面一行的最后一天是第 2 天。
示例 2：
输入：row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]] 输出：1 解释：上图描述了矩阵从第 0 天开始是如何变化的。 可以从最上面一行到最下面一行的最后一天是第 1 天。
示例 3：
输入：row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]] 输出：3 解释：上图描述了矩阵从第 0 天开始是如何变化的。 可以从最上面一行到最下面一行的最后一天是第 3 天。
提示：
2 <= row, col <= 2 * 1044 <= row * col <= 2 * 104cells.length == row * col1 <= ri <= row1 <= ci <= colcells中的所有格子坐标都是 唯一 的。
逆序并查集。
并查集模板：
模板 1——朴素并查集：
# 初始化，p存储每个点的父节点
p = list(range(n))
# 返回x的祖宗节点
def find(x):
if p[x] != x:
# 路径压缩
p[x] = find(p[x])
return p[x]
# 合并a和b所在的两个集合
p[find(a)] = find(b)模板 2——维护 size 的并查集：
# 初始化，p存储每个点的父节点，size只有当节点是祖宗节点时才有意义，表示祖宗节点所在集合中，点的数量
p = list(range(n))
size = [1] * n
# 返回x的祖宗节点
def find(x):
if p[x] != x:
# 路径压缩
p[x] = find(p[x])
return p[x]
# 合并a和b所在的两个集合
if find(a) != find(b):
size[find(b)] += size[find(a)]
p[find(a)] = find(b)模板 3——维护到祖宗节点距离的并查集：
# 初始化，p存储每个点的父节点，d[x]存储x到p[x]的距离
p = list(range(n))
d = [0] * n
# 返回x的祖宗节点
def find(x):
if p[x] != x:
t = find(p[x])
d[x] += d[p[x]]
p[x] = t
return p[x]
# 合并a和b所在的两个集合
p[find(a)] = find(b)
d[find(a)] = distanceclass Solution:
def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
n = row * col
p = list(range(n + 2))
grid = [[False] * col for _ in range(row)]
top, bottom = n, n + 1
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
def check(i, j):
return 0 <= i < row and 0 <= j < col and grid[i][j]
for k in range(len(cells) - 1, -1, -1):
i, j = cells[k][0] - 1, cells[k][1] - 1
grid[i][j] = True
for x, y in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
if check(i + x, j + y):
p[find(i * col + j)] = find((i + x) * col + j + y)
if i == 0:
p[find(i * col + j)] = find(top)
if i == row - 1:
p[find(i * col + j)] = find(bottom)
if find(top) == find(bottom):
return k
return 0class Solution {
private int[] p;
private int row;
private int col;
private boolean[][] grid;
private int[][] dirs = new int[][] {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
public int latestDayToCross(int row, int col, int[][] cells) {
int n = row * col;
this.row = row;
this.col = col;
p = new int[n + 2];
for (int i = 0; i < p.length; ++i) {
p[i] = i;
}
grid = new boolean[row][col];
int top = n, bottom = n + 1;
for (int k = cells.length - 1; k >= 0; --k) {
int i = cells[k][0] - 1, j = cells[k][1] - 1;
grid[i][j] = true;
for (int[] e : dirs) {
if (check(i + e[0], j + e[1])) {
p[find(i * col + j)] = find((i + e[0]) * col + j + e[1]);
}
}
if (i == 0) {
p[find(i * col + j)] = find(top);
}
if (i == row - 1) {
p[find(i * col + j)] = find(bottom);
}
if (find(top) == find(bottom)) {
return k;
}
}
return 0;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
private boolean check(int i, int j) {
return i >= 0 && i < row && j >= 0 && j < col && grid[i][j];
}
}class Solution {
public:
vector<int> p;
int dirs[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
int row, col;
int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
int n = row * col;
this->row = row;
this->col = col;
p.resize(n + 2);
for (int i = 0; i < p.size(); ++i) p[i] = i;
vector<vector<bool>> grid(row, vector<bool>(col, false));
int top = n, bottom = n + 1;
for (int k = cells.size() - 1; k >= 0; --k) {
int i = cells[k][0] - 1, j = cells[k][1] - 1;
grid[i][j] = true;
for (auto e : dirs) {
if (check(i + e[0], j + e[1], grid)) {
p[find(i * col + j)] = find((i + e[0]) * col + j + e[1]);
}
}
if (i == 0) p[find(i * col + j)] = find(top);
if (i == row - 1) p[find(i * col + j)] = find(bottom);
if (find(top) == find(bottom)) return k;
}
return 0;
}
bool check(int i, int j, vector<vector<bool>>& grid) {
return i >= 0 && i < row && j >= 0 && j < col && grid[i][j];
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
};var p []int
func latestDayToCross(row int, col int, cells [][]int) int {
n := row * col
p = make([]int, n+2)
for i := 0; i < len(p); i++ {
p[i] = i
}
grid := make([][]bool, row)
for i := 0; i < row; i++ {
grid[i] = make([]bool, col)
}
top, bottom := n, n+1
dirs := [4][2]int{{0, -1}, {0, 1}, {1, 0}, {-1, 0}}
for k := len(cells) - 1; k >= 0; k-- {
i, j := cells[k][0]-1, cells[k][1]-1
grid[i][j] = true
for _, e := range dirs {
if check(i+e[0], j+e[1], grid) {
p[find(i*col+j)] = find((i+e[0])*col + j + e[1])
}
}
if i == 0 {
p[find(i*col+j)] = find(top)
}
if i == row-1 {
p[find(i*col+j)] = find(bottom)
}
if find(top) == find(bottom) {
return k
}
}
return 0
}
func check(i, j int, grid [][]bool) bool {
return i >= 0 && i < len(grid) && j >= 0 && j < len(grid[0]) && grid[i][j]
}
func find(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}