题目描述

在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

返回必须翻转的 0 的最小数目。（可以保证答案至少是 1。）

样例

输入：[[0,1],[1,0]]
输出：1

输入：[[0,1,0],[0,0,0],[0,0,1]]
输出：2

输入：[[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]]
输出：1

注意

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

算法

(DFS, BFS) $O(nm)$

1. 首先可以通过 DFS 找到第一座岛，即从某个为 1 的点开始 DFS，然后把遍历到的点改为 0，直到四连通范围内不再存在为 1 的点。
2. 将第一座岛的所有点加入队列，距离设置为 0，开始 BFS 整个地图。
3. 最后只需要从地图上还是 1 的点中（一定是第二座岛），寻找距离最短的点。然后将距离减 1 即可。

时间复杂度

• DFS 和 BFS 的时间复杂度都是 $O(nm)$，故总时间复杂度为 $O(nm)$。

C++ 代码

class Solution {
public:
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    void dfs(int x, int y, int n, int m,
             queue<pair<int, int>> &q,
             vector<vector<int>> &A,
             vector<vector<int>> &dis) {

        A[x][y] = 0;
        dis[x][y] = 0;
        q.push(make_pair(x, y));
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 0 || tx >= n || ty < 0 || ty >= m || A[tx][ty] == 0)
                continue;
            dfs(tx, ty, n, m, q, A, dis);
        }
    }

    int shortestBridge(vector<vector<int>>& A) {
        int n = A.size(), m = A[0].size();
        queue<pair<int, int>> q;
        vector<vector<int>> dis(n, vector<int>(m, n * m));
        bool flag = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                if (A[i][j] == 1) {
                    dfs(i, j, n, m, q, A, dis);
                    flag = true;
                    break;
                }
            if (flag)
                break;
        }

        while (!q.empty()) {
            pair<int, int> sta = q.front();
            q.pop();
            int x = sta.first, y = sta.second;
            for (int i = 0; i < 4; i++) {
                int tx = x + dx[i], ty = y + dy[i];
                if (tx < 0 || tx >= n || ty < 0 || ty >= m)
                    continue;
                if (dis[tx][ty] > dis[x][y] + 1) {
                    dis[tx][ty] = dis[x][y] + 1;
                    q.push(make_pair(tx, ty));
                }
            }
        }

        int ans = n * m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (A[i][j] == 1)
                    ans = min(ans, dis[i][j] - 1);

        return ans;   
    }
};