var dir4 = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func latestDayToCross(row, col int, cells [][]int) int {
top := row * col
bottom := top + 1
uf := newUnionFind(bottom + 1)
land := make([][]bool, row)
for i := range land {
land[i] = make([]bool, col)
}
// 倒序遍历天数，如果最上和最下连通了，这一天就是答案
for day := len(cells) - 1; ; day-- {
p := cells[day]
r, c := p[0]-1, p[1]-1
v := r*col + c
for _, d := range dir4 {
if x, y := r+d.x, c+d.y; 0 <= x && x < row && 0 <= y && y < col && land[x][y] { // 与四周的陆地相连
uf.merge(v, x*col+y)
}
}
land[r][c] = true // 将该位置标记为陆地
if r == 0 {
uf.merge(v, top) // 与最上面相连
} else if r == row-1 {
uf.merge(v, bottom) // 与最下面相连
}
if uf.same(top, bottom) {
return day // 最上和最下连通了，返回答案
}
}
}
// 并查集模板
type uf struct {
fa []int
}
func newUnionFind(n int) uf {
fa := make([]int, n)
for i := range fa {
fa[i] = i
}
return uf{fa}
}
func (u uf) find(x int) int {
if u.fa[x] != x {
u.fa[x] = u.find(u.fa[x])
}
return u.fa[x]
}
func (u uf) merge(from, to int) {
x, y := u.find(from), u.find(to)
if x != y {
u.fa[x] = y
}
}
func (u uf) same(x, y int) bool {
return u.find(x) == u.find(y)
}
class Solution {
int[] p;
int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int latestDayToCross(int m, int n, int[][] cells) {
p = new int[m * n + 2];
int s = m * n;
int t = m * n + 1;
for (int i = 0; i < p.length; i++) {
p[i] = i;
}
// 是否是陆地
boolean[] vis = new boolean[m * n];
for (int i = cells.length - 1; i >= 0; i--) {
// 即将变成陆地的格子
int[] cell = cells[i];
int f = (cell[0] - 1) * n + cell[1] - 1;
vis[f] = true;
// 连通上下左右
for (int[] dir : dirs) {
int x = dir[0] + cell[0] - 1;
int y = dir[1] + cell[1] - 1;
int d = x * n + y;
if (y < 0 || y >= n) continue;
// 判断是不是超级节点
if (x == -1) {
union(f, s);
} else if (x == m) {
union(f, t);
} else {
// 如果是陆地就连接
if (vis[d]) {
union(f, d);
}
}
}
if (find(s) == find(t)) return i;
}
return 0;
}
public int find(int x) {
while (x != p[x]) {
x = p[x] = p[p[x]];
}
return x;
}
public void union(int x, int y) {
int i = find(x);
int j = find(y);
if (i != j) {
p[i] = j;
}
}
}
# 并查集模板
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.size = [1] * n
self.n = n
# 当前连通分量数目
self.setCount = n
def findset(self, x: int) -> int:
if self.parent[x] == x:
return x
self.parent[x] = self.findset(self.parent[x])
return self.parent[x]
def unite(self, x: int, y: int) -> bool:
x, y = self.findset(x), self.findset(y)
if x == y:
return False
if self.size[x] < self.size[y]:
x, y = y, x
self.parent[y] = x
self.size[x] += self.size[y]
self.setCount -= 1
return True
def connected(self, x: int, y: int) -> bool:
x, y = self.findset(x), self.findset(y)
return x == y
class Solution:
def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
# 编号为 n 的节点是超级节点 s
# 编号为 n+1 的节点是超级节点 t
n = row * col
uf = UnionFind(n + 2)
valid = [[0] * col for _ in range(row)]
ans = 0
for i in range(n - 1, -1, -1):
x, y = cells[i][0] - 1, cells[i][1] - 1
valid[x][y] = 1
# 并查集是一维的，(x, y) 坐标是二维的，需要进行转换
idx = x * col + y
if x - 1 >= 0 and valid[x - 1][y]:
uf.unite(idx, idx - col)
if x + 1 < row and valid[x + 1][y]:
uf.unite(idx, idx + col)
if y - 1 >= 0 and valid[x][y - 1]:
uf.unite(idx, idx - 1)
if y + 1 < col and valid[x][y + 1]:
uf.unite(idx, idx + 1)
if x == 0:
uf.unite(idx, n)
if x == row - 1:
uf.unite(idx, n + 1)
if uf.connected(n, n + 1):
ans = i
break
return ans
class Solution:
def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
left, right, ans = 0, row * col, 0
while left <= right:
mid = (left + right) // 2
grid = [[1] * col for _ in range(row)]
for x, y in cells[:mid]:
grid[x - 1][y - 1] = 0
q = deque()
for i in range(col):
if grid[0][i]:
q.append((0, i))
grid[0][i] = 0
found = False
while q:
x, y = q.popleft()
for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
if 0 <= nx < row and 0 <= ny < col and grid[nx][ny]:
if nx == row - 1:
found = True
break
q.append((nx, ny))
grid[nx][ny] = 0
if found:
ans = mid
left = mid + 1
else:
right = mid - 1
return ans
