[LeetCode] 934. Shortest Bridge 最短的橋梁

In a given 2D binary array `A`, there are two islands. (An island is a 4-directionally connected group of `1`s not connected to any other 1s.)

Now, we may change

s to

s so as to connect the two islands together to form 1 island.

Return the smallest number of

s that must be flipped. (It is guaranteed that the answer is at least 1.)

Example 1:

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

Example 2:

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

Example 3:

Input: [[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

Note:

1 <= A.length = A[0].length <= 100
A[i][j] == 0 or A[i][j] == 1

這道題說是有一個隻有0和1的二維數組，其中連在一起的1表示島嶼，現在假定給定的數組中一定有兩個島嶼，問最少需要把多少個0變成1才能使得兩個島嶼相連。在 LeetCode 中關于島嶼的題目還不少，但是萬變不離其宗，核心都是用 DFS 或者 BFS 來解，有些還可以用聯合查找 Union Find 來做。這裡要求的是最小值，首先預定了一個 BFS，這就相當于洪水擴散一樣，一圈一圈的，用的就是 BFS 的層序周遊。好，現在确定了這點後，再來想，這裡并不是從某個點開始擴散，而是要從一個島嶼開始擴散，那麼這個島嶼的所有的點都是 BFS 的起點，都是要放入到 queue 中的，是以要先來找出一個島嶼的所有點。找的方法就是周遊數組，找到第一個1的位置，然後對其調用 DFS 或者 BFS 來找出所有相連的1，先來用 DFS 的方法，對第一個為1的點調用遞歸函數，将所有相連的1都放入到一個隊列 queue 中，并且将該點的值改為2，然後使用 BFS 進行層序周遊，每周遊一層，結果 res 都增加1，當遇到1時，直接傳回 res 即可，參見代碼如下：

解法一：

class Solution {
public:
    int shortestBridge(vector<vector<int>>& A) {
        int res = 0, n = A.size(), startX = -1, startY = -1;
        queue<int> q;
        vector<int> dirX{-1, 0, 1, 0}, dirY = {0, 1, 0, -1};
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (A[i][j] == 0) continue;
                startX = i; startY = j;
                break;
            }
            if (startX != -1) break;
        }
        helper(A, startX, startY, q);
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                int t = q.front(); q.pop();
                for (int k = 0; k < 4; ++k) {
                    int x = t / n + dirX[k], y = t % n + dirY[k];
                    if (x < 0 || x >= n || y < 0 || y >= n || A[x][y] == 2) continue;
                    if (A[x][y] == 1) return res;
                    A[x][y] = 2;
                    q.push(x * n + y);
                }
            }
            ++res;
        }
        return res;
    }
    void helper(vector<vector<int>>& A, int x, int y, queue<int>& q) {
        int n = A.size();
        if (x < 0 || x >= n || y < 0 || y >= n || A[x][y] == 0 || A[x][y] == 2) return;
        A[x][y] = 2;
        q.push(x * n + y);
        helper(A, x + 1, y, q);
        helper(A, x, y + 1, q);
        helper(A, x - 1, y, q);
        helper(A, x, y - 1, q);
    }
};

我們也可以使用 BFS 來找出所有相鄰的1，再加上後面的層序周遊的 BFS，總共需要兩個 BFS，注意這裡第一個 BFS 不需要是層序周遊的，而第二個 BFS 是必須層序周遊，可以對比一下看一下這兩種寫法有何不同，參見代碼如下：

解法二：

class Solution {
public:
    int shortestBridge(vector<vector<int>>& A) {
        int res = 0, n = A.size();
        queue<int> q, que;
        vector<int> dirX{-1, 0, 1, 0}, dirY = {0, 1, 0, -1};
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (A[i][j] == 0) continue;
                A[i][j] = 2;
                que.push(i * n + j);
                break;
            }
            if (!que.empty()) break;
        }
        while (!que.empty()) {
            int t = que.front(); que.pop();
            q.push(t);
            for (int k = 0; k < 4; ++k) {
                int x = t / n + dirX[k], y = t % n + dirY[k];
                if (x < 0 || x >= n || y < 0 || y >= n || A[x][y] == 0 || A[x][y] == 2) continue;
                A[x][y] = 2;
                que.push(x * n + y);
            }
        }
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                int t = q.front(); q.pop();
                for (int k = 0; k < 4; ++k) {
                    int x = t / n + dirX[k], y = t % n + dirY[k];
                    if (x < 0 || x >= n || y < 0 || y >= n || A[x][y] == 2) continue;
                    if (A[x][y] == 1) return res;
                    A[x][y] = 2;
                    q.push(x * n + y);
                }
            }
            ++res;
        }
        return res;
    }
};

Github 同步位址:

https://github.com/grandyang/leetcode/issues/934

類似題目：

Making A Large Island

Number of Distinct Islands II

Max Area of Island

Number of Distinct Islands

Island Perimeter

Number of Islands II

Number of Islands

參考資料：

https://leetcode.com/problems/shortest-bridge/

https://leetcode.com/problems/shortest-bridge/discuss/189315/Java-DFS%2BBFS-traverse-the-2D-array-once

https://leetcode.com/problems/shortest-bridge/discuss/189293/C%2B%2B-BFS-Island-Expansion-%2B-UF-Bonus

https://leetcode.com/problems/shortest-bridge/discuss/189321/Java-DFS-find-the-island-greater-BFS-expand-the-island

[LeetCode All in One 題目講解彙總(持續更新中...)](https://www.cnblogs.com/grandyang/p/4606334.html)

喜歡請點贊，疼愛請打賞❤️~.~

微信打賞

Venmo 打賞