1970

暴力

直接for loop + bfs/dfs 但是TLE

Binary Search

因为如果路被堵住那么后面所有的路都被堵住，所以可以用bs加速， 过了

Union Find

看了题解，天才想法T T 从后往前遍历找从上到下的一条水路，如果有这条水路这意味着在这天之前有这条路(因为这条路从今天开始)，return 这天(因为还有第0天)

以这个思想可以bfs/dfs (感觉worst case是暴力)但更推荐与union find，将已经出现过的水路按陆路行走路径链接起来比 bfs/dfs快很多(ps: bfs/dfs需要每次跑完从curr到last所有的cells, 而union find已经记录好了)

• 看到topic有union find的时候我还没有想到的一点是top和bottom该怎么放在一个set里，看了题解以后才意识到最简单的方法就是，直接将他们的parent initial 成一个top 和 bottom的值，然后find top == find bottom 就说明链接到一起了 时间复杂度仅仅是O(nlogn*)