1970. 你能穿过矩阵的最后一天

func latestDayToCross(row int, col int, cells [][]int) int {
	grid := make([][]int, row)
	for i := range grid {
		grid[i] = make([]int, col)
	}
	total := row * col
	initUF(total + 2)
	left := total
	right := total + 1
	getID := func(r, c int) int {
		return r*col + c
	}
	for r := 0; r < row; r++ {
		id := getID(r, 0)
		union(id, left)
		id = getID(r, col-1)
		union(id, right)
	}
	for i, cell := range cells {
		r, c := cell[0]-1, cell[1]-1
		grid[r][c] = 1
		// 联通8个方向上的相邻1
		for dr := -1; dr <= 1; dr++ {
			for dc := -1; dc <= 1; dc++ {
				if dr == 0 && dc == 0 {
					continue
				}
				nr, nc := r+dr, c+dc
				if nr < 0 || nr >= row || nc < 0 || nc >= col || grid[nr][nc] == 0 {
					continue
				}
				union(getID(r, c), getID(nr, nc))
				if find(left) == find(right) {
					return i
				}
			}
		}
	}
	return len(cells)
}

var uf []int

func initUF(n int) {
	uf = make([]int, n)
	for i := range uf {
		uf[i] = i
	}
}
func find(x int) int {
	for x != uf[x] {
		x, uf[x] = uf[x], uf[uf[x]]
	}
	return x
}
func union(x, y int) {
	x, y = find(x), find(y)
	uf[x] = y
}

func Test_latestDayToCross(t *testing.T) {
	type args struct {
		row   int
		col   int
		cells [][]int
	}
	tests := []struct {
		name string
		args args
		want int
	}{
		{args: args{6, 2, [][]int{{2, 1}, {4, 2}, {6, 2}, {4, 1}, {1, 2}}}, want: 3},
	}
	for _, tt := range tests {
		if got := latestDayToCross(tt.args.row, tt.args.col, tt.args.cells); got != tt.want {
			t.Errorf("%q. latestDayToCross() = %v, want %v", tt.name, got, tt.want)
		}
	}
}