Leetcode 1970. Last Day Where You Can Still Cross

Difficulty: Hard (5 personal rank)
Keywords: DSU, binary search

題目

有一個全是陸地的grids，每天都會有一格被水填滿，問最多有幾天，能從grids頂端的任何一點走陸路抵達底端的任何一點。

• row：row size
• col：col size
• cells: cells[i]為第i天被水覆蓋的新區域

row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]

討論

我想大家直覺都是DSU，但這題的難點在於，如何從一個DSU中去比對最頂層是否連通最底層。換句話說，如何取比對：比對某個子集合A的任何一點跟另一個子集合B的任何一點連通。

一種做法是看看最頂層的格子點跟最底層的格子點有沒有交集的group，但是這顯然不是出這題的用意。

有一個很聰明的作法就是，假設將所有A跟S接起來，也將所有B跟T接起來，其中S跟T是我新創的兩個假的節點，則未來只要每次都比對S和T是否連通即可。

如下面很醜的示意圖，一個圖中有若干節點及若干邊，問紅色節點跟藍色節點有沒有任何一點是相通的，我們可以只比對S和T即可。

很醜的示意圖

想法1： binary search + DSU

由於被水覆蓋的區域只會隨著天數增加越來越多，因此用bs去逼近天數不失為一個方式，決定一個天數之後就能用一些方式判定能否通過。

想法2：DSU

由於已經有一個O(1)的方式來判定兩群集合是否存在連線，這題就變得十分單純，逐步往grid增加水，看看到第幾天左右完全連通。

不過大部分的人應該是否過來做，假設最後一天全部都是水，往前推進逐步增加陸地，看看到第幾天陸地上下連通。時間複雜度 O(row*col)

程式碼2

從最後一天往前逐日增加陸地，S和E分別連到最頂端及最底端的所有點。

• 時間複雜度：O(row * col)
• 空間複雜度：O( row * col)