778. 水位上升的泳池中游泳

func swimInWater(grid [][]int) int

func canReach(h int, grid [][]int) bool {
	const maxN = 50
	n := len(grid)
	// 找相邻位置的一个技巧，减少代码量
	// 遍历dr和dc用原来的横纵坐标加上对应dr、dc里的坐标即得到上下左右相邻位置之一的坐标
	// 也可以把dr、dc合并为一个二维切片（数组）
	dr := []int{1, -1, 0, 0}
	dc := []int{0, 0, 1, -1}
	visited := [maxN][maxN]bool{} // 标识已经访问过的平台，也可以用map；其实应该是n*n大小，但是用n的话代码要多几行，需要遍历初始化每一行
	visited[0][0] = true
	set := list.New()
	set.PushBack([]int{0, 0}) // 用长度为2的切片代表一个点；初始位置放入集合
	for set.Len() > 0 {
		pos := set.Remove(set.Back()).([]int)
		row, column := pos[0], pos[1]
		if row == n-1 && column == n-1 {
			return true
		}
		for i := 0; i < len(dr); i++ {
			nextRow, nextColumn := row+dr[i], column+dc[i]
			if nextRow >= 0 && nextRow < n && nextColumn >= 0 && nextColumn < n &&
				!visited[nextRow][nextColumn] && grid[nextRow][nextColumn] <= h {
				set.PushBack([]int{nextRow, nextColumn})
				visited[nextRow][nextColumn] = true
			}
		}
	}
	return false
}

/*
不用二分法的朴素实现，时间复杂度O(n^2*(max-grid[0][0]+1))
leetcode实测会花费376 ms，其他解法的时间在12-28ms内
*/
func swimInWater0(grid [][]int) int {
	start, end := grid[0][0], max(grid)
	for i := start; i < end; i++ {
		if canReach(i, grid) {
			return i
		}
	}
	return end
}

// 二分法，用标准库,减少点代码量
func swimInWater2(grid [][]int) int {
	return sort.Search(max(grid)+1, func(i int) bool { // 这里其实有点浪费，在[0,max]的区间里搜所的
		if i < grid[0][0] {
			return false
		}
		return canReach(i, grid)
	})
}

func max(grid [][]int) int {
	result := 0
	for r := 0; r < len(grid); r++ {
		for c := 0; c < len(grid); c++ {
			if grid[r][c] > result {
				result = grid[r][c]
			}
		}
	}
	return result
}

// 平台结构体，方便自定义heap实现
type pos struct {
	height, r, c int // 高度和横纵坐标
}

func swimInWater(grid [][]int) int {
	const maxN = 50
	n := len(grid)
	dr := []int{1, -1, 0, 0}
	dc := []int{0, 0, 1, -1}
	visited := [maxN][maxN]bool{}
	result := 0
	pq := &posHeap{}
	heap.Push(pq, pos{height: grid[0][0], r: 0, c: 0})
	visited[0][0] = true

	for pq.Len() > 0 {
		info := heap.Pop(pq).(pos) // 游到当前最低的平台上
		if grid[info.r][info.c] > result {
			result = grid[info.r][info.c]
		}
		if info.r == n-1 && info.c == n-1 { // 终点
			break
		}
		for i := 0; i < len(dr); i++ {
			r, c := info.r+dr[i], info.c+dc[i]
			if r >= 0 && r < n && c >= 0 && c < n && !visited[r][c] {
				heap.Push(pq, pos{height: grid[r][c], r: r, c: c})
				visited[r][c] = true
			}
		}
	}
	return result
}

type posHeap []pos

func (h posHeap) Len() int            { return len(h) }
func (h posHeap) Less(i, j int) bool  { return h[i].height < h[j].height }
func (h posHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *posHeap) Push(x interface{}) { *h = append(*h, x.(pos)) }
func (h *posHeap) Pop() interface{} {
	pos := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return pos
}

func swimInWater(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	edges := make([]edge, 0, m*n*2)
	for r, row := range grid {
		for c, _ := range row {
			id := r*n + c
			if r > 0 {
				topId := (r-1)*n + c
				edges = append(edges, edge{id, topId, max(grid[r][c], grid[r-1][c])})
			}
			if c > 0 {
				leftId := r*n + c - 1
				edges = append(edges, edge{id, leftId, max(grid[r][c], grid[r][c-1])})
			}
		}
	}
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].val < edges[j].val
	})
	makeUnionFind(m * n)
	for _, e := range edges {
		union(e.pos1, e.pos2)
		if find(0) == find(m*n-1) {
			return e.val
		}
	}
	return 0
}

type edge struct {
	pos1, pos2, val int
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

var uf []int

func makeUnionFind(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)
	if x == y {
		return
	}
	uf[x] = y
}