934. Shortest Bridge

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

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s 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. 1 <= A.length = A[0].length <= 100

  2. 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>& 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>& A, int x, int y, queue& 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>& 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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation