778. Swim in Rising Water
思路:
用一個minimum heap來記錄目前到過的點哪個點海拔最低
每次都把海拔最低的點pop出來
並且記錄這些被pop出來的海拔中最大值
當抵達右下角時就可以停了
最後回傳這條路徑中最大的海拔
golang code :
type point struct {
x int
y int
}
type maxHeap struct {
arr []point
grid [][]int
}
func (this maxHeap) Len() int { return len(this.arr) }
func (this maxHeap) Less(i, j int) bool {
return this.grid[this.arr[i].x][this.arr[i].y] < this.grid[this.arr[j].x][
this.arr[j].y]
}
func (this maxHeap) Swap(i, j int) {
this.arr[i], this.arr[j] = this.arr[j], this.arr[i]
}
func (this *maxHeap) Pop() interface{} {
n := len(this.arr)
res := this.arr[n-1]
(*this).arr = (*this).arr[:n-1]
return res
}
func (this *maxHeap) Push(x interface{}) {
(*this).arr = append((*this).arr, x.(point))
}
func swimInWater(grid [][]int) int {
h := maxHeap{[]point{}, grid}
n, m := len(grid), len(grid[0])
heap.Push(&h, point{0, 0})
ans := 0
direction, visit := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, make([]bool, n
*m)
visit[0] = true
for {
curPoint := heap.Pop(&h).(point)
ans = max(ans, grid[curPoint.x][curPoint.y])
if curPoint.x == n-1 && curPoint.y == m-1 {
break
}
for _, val := range direction {
nextX := curPoint.x + val[0]
nextY := curPoint.y + val[1]
if nextX > -1 && nextY > -1 && nextX < n && nextY < m && !visit[nextX*m+
nextY] {
visit[nextX*m+nextY] = true
heap.Push(&h, point{nextX, nextY})
}
}
}
return ans
}