Back to Leetcode

Readme

BFS/778.Swim-in-Rising-Water/Readme.md

latest1022 B
Original Source

778.Swim-in-Rising-Water

此题和407.Trapping-Rain-Water-II非常像,可以比照学习。

我们想象从起点开始,人随着海平面的高度上升。我们将起点周围的格子作为“堤岸”放入一个优先队列里,PQ里面的元素按照高度从低到高。显然,当海平面高度cur涨至PQ的最小元素高度时,就会从那里“决堤而入”,这时候那个决堤口周围的新格子就可以作为新“堤岸”放入PQ。

如果下一个回合PQ里面的最小元素也小于等于cur时,说明那个格子也会被“淹没”,我们继续将那个格子周围的格子作为“堤岸”加入队列。如果下一个回合PQ里面的最小元素大于cur时,那么就需要让整个海平面cur继续上涨,直至到达PQ里面的最小元素高度,从而引发又一次“决堤泛滥”的过程。

整个海平面上涨的过程持续到我们能淹没右下角的格子为止。

Leetcode Link