leetcode-934：最短的桥_leecode 最短的桥

题目

题目连接

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：A = [[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
2

解题

方法一：BFS

1.首先遍历，找到其中岛屿的一个点
2.将第一步中找到的那个岛屿全部标记成-1
3.从第一个岛屿出发，开始BFS(层序遍历)，一但遇到1，就说明遇到第二个岛屿了

class Solution {
public:
    vector<vector<int>> dirs={{-1,0},{1,0},{0,1},{0,-1}};

    int shortestBridge(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        //找到其中一个岛屿的点
        pair<int,int> startPoint;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    startPoint={i,j};
                    goto OUT;
                }
            }
        }
        OUT:
        //BFS
        //将找到的其中一个岛屿全部标记成-1，并把它全部存入q2中
        queue<pair<int,int>> q1;//用于bfs
        queue<pair<int,int>> q2;//将节点存起来，用于之后的bfs初始值
        grid[startPoint.first][startPoint.second]=-1;
        q1.push(startPoint);
        while(!q1.empty()){
            auto [x,y]=q1.front();
            q2.push({x,y});
            q1.pop();
            for(vector<int>& dir:dirs){
                int nx=x+dir[0];
                int ny=y+dir[1];
                if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]==1){
                    q1.push({nx,ny});
                    grid[nx][ny]=-1;
                }
            }
        }
        //BFS
        //-1表示已经访问过的点，0表示还未访问过的点，1表示目的岛屿
        //找到值为1的点就说明找到了
        int count=0;
        while(!q2.empty()){
            int l=q2.size();
            for(int i=0;i<l;i++){
                auto [x,y]=q2.front();
                q2.pop();
                for(vector<int>& dir:dirs){
                    int nx=x+dir[0];
                    int ny=y+dir[1];
                    if(nx>=0&&nx<m&&ny>=0&&ny<n){
                        if(grid[nx][ny]==1) return count;
                        else if(grid[nx][ny]==0){
                            q2.push({nx,ny});
                            grid[nx][ny]=-1;
                        }
                    }
    
                }
            }
            count++;  
        }
        return -1;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65