0934. Shortest Bridge (Medium)

寫在前面

(基礎+進階+面試篇)從 LeetCode 學演算法 + 面試成功指南**

(3591元 特價中: 2023/06/30 23:59後截止) 
https://hiskio.com/bundles/eCP23B397?s=tc

(3990元 長期有效) https://bit.ly/lc2022all

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/lc2022adv

Question

You are given an n x n binary matrix grid where 1 represents land and 0 represents water.

An island is a 4-directionally connected group of 1’s not connected to any other 1’s. There are ** exactly two islands** in grid.

You may change 0’s to 1’s to connect the two islands to form one island .

Return the smallest number of 0’s you must flip to connect the two islands.

Example 1

1
2

Input: grid = [[0,1],[1,0]]
Output: 1

Example 2

1
2

Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3

1
2

Input: grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Constraints

• n == grid.length == grid[i].length
• 2 <= n <= 100
• grid[i][j] is either 0 or 1.
• There are exactly two islands in grid.

分析/解題

給定一個 n x n 的 binary 矩陣 grid，當中 1 代表陸地，0 代表水。
一個 island (島嶼) 的定義是指一組在四個方向和其他的1相連的群組，
且沒有再和其他1相連(也就是中間經過1的都算是同一塊島嶼)。
在 grid 中恰好兩塊島嶼。
你可以將0變成1用來連接兩塊島嶼，以形成一塊島嶼，
試回傳要翻轉0到1使得兩塊島嶼連接的最少所需的數目。

好久不見了！

這題算是比較特別的題目，因為比較好的解法會是DFS和BFS都用上，
一個用來找到第一整塊島嶼，另一個用來連接。

就題目而言，從0翻到1，其實就是一個搭橋的概念，
單就grid上考慮，那麼我們肯定是從兩個島距離最近的點來搭會最好，
但怎麼知道哪兩個點距離最近呢？

如果兩塊島嶼都是完整矩形的話，
或許我們還可以從邊與邊的垂直距離來做文章，
也還有一些比較簡單的計算方法(比如下圖取兩點的垂直+水平距離)
(如果水平或垂直方向有重合的話則只計di或dj)

取最近的兩點垂直距離+水平距離(也有可能其中一個方向不用計)

但.…..它們並不一定是矩形XD"
所以有可能出現像這樣子的狀況，然後旁邊可能全是不規則形狀，
無法用矩形算完：

看圖會知道算哪個點，但究竟要娶幾個點才能算呢？

所以既然無法知道兩塊島嶼長什麼樣子，也不知道規不規則，
那只能回到笨方法了：
先找到其中一塊島嶼，再從這塊島嶼的邊界往外找(搭橋)。

我們嘗試來列出解題步驟：

1. 取得grid的長寬r, c (沒錯，這題其實就算不是正方形的grid應該也可以做)
2. 先遍歷找到grid上任意一個值為1的點(i, j)，
   這個點肯定是其中一塊島上的陸地
3. 從(i, j)開始進行DFS往四方探索陸地，同時將所有途經的陸地標為2
   (標成2的意義是為了可以和另一塊島嶼的陸地區分開來)；
4. 在步驟3的探索中，如果碰到0時，
   把和0相接的陸地座標記到一個queue 裡面
   (代表這是第一塊陸地的臨水的邊界)
5. 完成3, 4後，我們會得到一個queue，當中全是第一個島嶼的臨水的邊界 ，
   作為我們搭橋的出發點，這裡設定我們要求的答案step為0
6. 當queue中有值的時候，持續操作以下步驟：
7. 取得當前queue的長度L，進行一個L次的迴圈：
8. 從queue中取出一組座標(i, j)
9. 從(i, j)往四個方向看，如果沒有超出grid的話，檢查以下可能：
   9-1. 如果值是1，則代表成功接通，這時候直接回傳step作為答案即可
   9-2. 如果值是0，則代表繼續搭橋，將新座標放到queue當中，
   並且將這個位置的值標為-1(代表已經走過了)
10. 步驟7的迴圈結束後，將step遞增1，接下來回到6檢查是否要繼續
11. 雖然題目設定上一直都是找得到解答的，但如果找不到解答的話，
    離開步驟6的迴圈後，則應該要回傳-1，表示找不到能搭建的橋
    (也就是grid可能被給成只有一塊土地)

在上面的解題步驟中，步驟34是DFS ，
目的在於要找到第一塊島嶼，記錄邊界，
並將其值改動成2，用來跟第二塊島嶼區別；
而步驟610則是BFS ，
用來從邊界開始往外嘗試搭橋，
因此我們可以在找到連接到第二塊島嶼的時候，
因為一次是每種可能都走一步的特性，確定最小所需的步數，
也就是我們所要求的答案。

依此，寫成程式碼如下。

Python

為求簡單，這邊我們直接將grid改名為A，避免寫太多次。
我們可以利用簡單的dirs串列來標定四個方向，
從而縮減每次寫+1和-1的部分，
這個小技巧應該常碰到類似題目的同學大多看過。
另外，我們使用了一個set start，用來幫我們自動化簡加入的座標，
因為我們有可能加同樣的座標到queue裡面，
使用set可以有效避免這一點。

同時請留意到當A[x][y] == 0的時候，要加入的是(i, j)歐!
因為我們加入的是陸地的邊界(1)，而不是水(0)，
同理，後面起始的時候因為是從陸地開始起算，
所以step是從0而非從1開始。

Java

Java的部分則會稍微麻煩一點，
這邊將大多數的東西放在class variable的位置，
可以有效避免需要大量的傳遞參數；
Queue的部份我們使用ArrayDeque來處理，
那麼對應的取出和放入就會變成poll()和offer()。
(注意每次放入的時候都要產生一個新的int[]來放入)

另一方面，由於HashSet在Java當中用起來比較沒有像Python這麼彈性，
這邊採用visited的方式來處理，
我們將已經放入過q的(i, j)在visited中設定為true，
再每次檢查，即可得到相同效果。
此外，由於Java不接受回傳一個沒有回傳值的function，
因此27和28行會分成兩行來寫，先進行dfs完，再呼叫return。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(n²)/O(n²)，在長和寬均為n的狀況下，最多也就是掃完整個grid)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

想看看其他題目嗎？
歡迎從第零篇 找你想要的！

同時追蹤粉專以獲得更多新文章的通知：
跟著Desolve學程式

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/lc2022base