leetcode-934：最短的桥

题目

题目连接

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

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

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

示例 1：

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

示例 2：

输入：A = [[0,1,0],[0,0,0],[0,0,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

解题

方法一：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;

    }
};