楼主:
JIWP (JIWP)
2025-12-31 19:27:42今年最后一题leetcode
1970. Last Day Where You Can Still Cross
只要淹水的地方可以从第1行到最后1行连成一条线
直线可以从8个方向
右,右上、右下,左,左上,左下,上,下连起来
就可以保证没办法从top到bottom
所以用union find
在左右两边设一个墙
如果这两个墙能连起来那就能保证上下无法通行
c=0就要跟左墙连在一起
c=col-1要跟右墙连在一起
每一天都要去union 8个方向
最后检查左右墙是否连通
如果连通那就是这一天
golang code :
type unionFind struct{ parent []int }
func (this *unionFind) find(i int) int {
if (*this).parent[i] == i {
return i
}
(*this).parent[i] = this.find((*this).parent[i])
return (*this).parent[i]
}
func (this *unionFind) union(i, j int) {
p1, p2 := this.find(i), this.find(j)
if p1 != p2 {
this.parent[p1] = p2
}
}
func latestDayToCross(row int, col int, cells [][]int) int {
n := row * col
uf := unionFind{make([]int, n+2)}
for i := 0; i < n+2; i++ {
uf.parent[i] = i
}
grid := make([][]bool, row)
for i := 0; i < row; i++ {
grid[i] = make([]bool, col)
}
leftWall, rightWall := n, n+1
for time, cell := range cells {
r, c := cell[0]-1, cell[1]-1
cur := r*col + c
grid[r][c] = true
if c == 0 {
uf.union(cur, leftWall)
}
if c == col-1 {
uf.union(cur, rightWall)
}
for i := -1; i <= 1; i++ {
for j := -1; j <= 1; j++ {
nextR, nextC := r+i, c+j
if nextR < row && nextC < col && nextR > -1 && nextC > -1 && grid[nextR][
nextC] {
uf.union(cur, nextR*col+nextC)
}
}
}
if uf.find(leftWall) == uf.find(rightWall) {
return time
}
}
return 0
}