Skip to main content

778

感觉好多图题的union find的solution都太过精妙一般来说太难想

这题我的做法就是bs+bfs

union find

将二维转成1位,然后用map或者数组去记录grid[i][j] 的位置i*n + j. 然后从时间0开始遍历,时间t 所有的高度为t的格子都可以尝试向四边游泳,直接将他们merge起来,游完以后判断开始和终点是否共享一个parent(有路),不可以就继续进行。

dijkstra最短路

在做最短路的时候更新一下答案即可...写最短路太少了完全没有想到这个解法