934.最短的桥（广度优先搜索）

解题思路

方法1：暴力法
使用深度优先搜索，讲两个岛屿的坐标存储到两个数组中，然后用两个for遍历数组，找到最小置。
很暴力，时间和空间复杂度也很高。

class Solution {
    
public:
    int shortestBridge(vector<vector<int>>& grid) {
    
        int m=grid.size(),n=grid[0].size();
        vector<vector<bool>>visited(m,vector<bool>(n,false));
        vector<vector<int>>island1_axis,island2_axis;
        int whichIsland=1;
        for(int i=0;i<m;++i){
    
            for(int j=0;j<n;++j){
    
                if(!visited[i][j]&&grid[i][j]==1){
    
                    if(whichIsland==1){
    
                        ++whichIsland;
                        dfs(grid,visited,island1_axis,i,j);
                        continue;
                    }
                    if(whichIsland==2){
    
                        ++whichIsland;
                        dfs(grid,visited,island2_axis,i,j);
                    }
                }
            }
        }

        int min_cnt=INT_MAX;
        int cnt;
        for(auto &axis1:island1_axis){
    
            int x1=axis1[0],y1=axis1[1];
            for(auto &axis2:island2_axis){
    
                int x2=axis2[0],y2=axis2[1];
                cnt=abs(x1-x2)+abs(y1-y2)-1;
                if(cnt<min_cnt) min_cnt=cnt;
            }
        }

        return min_cnt;
    }

    void dfs(const vector<vector<int>> &grid,vector<vector<bool>> &visited,
                vector<vector<int>> &axis,int x,int y)
    {
    
        if(x>=0&&x<grid.size()&&y>=0&&y<grid[0].size()
            &&!visited[x][y]&&grid[x][y]==1){
    
                visited[x][y]=true;
                axis.push_back({
    x,y});
                dfs(grid,visited,axis,x-1,y);
                dfs(grid,visited,axis,x+1,y);
                dfs(grid,visited,axis,x,y-1);
                dfs(grid,visited,axis,x,y+1);
        }   
    }
};

法2：广度优先搜索
处理最短路径问题，使用广度优先搜索方法。
这个方法是看答案的，感觉很巧妙，以前没有想过这种方法，在此记录一下。
先通过深度优先搜索其中一个岛屿，并且将数字变为2，与另一座岛屿区分；然后再通过广度优先搜索，一层一层架桥，直到遇到另一座岛。

class Solution {
    
    vector<int>direction{
    -1,0,1,0,-1};
public:
    int shortestBridge(vector<vector<int>>& grid) {
    
        int m=grid.size(),n=grid[0].size();
        queue<pair<int,int>>points;
        //dfs寻找第一个岛屿，并把1全部赋值为2
        bool flipped=false;
        for(int i=0;i<m;++i){
    
            if(flipped) break;
            for(int j=0;j<n;++j){
    
                if(grid[i][j]==1){
    
                    dfs(points,grid,m,n,i,j);
                    flipped=true;
                    break;
                }
            }
        }

        //bfs寻找第二个岛屿，并把过程中经过的0赋值为2
        int x,y;
        int level=0;
        while(!points.empty()){
    
            //处理第一层0
            ++level;
            int n_points=points.size();
            while(n_points--){
    
                //遍历第一层所有的点
                auto [r,c]=points.front();
                points.pop();
                for(int k=0;k<4;++k){
    
                    x=r+direction[k],y=c+direction[k+1];
                    if(x>=0&&x<m&&y>=0&&y<n){
    
                        if(grid[x][y]==2){
    
                            //假如是2，啥也不做
                            continue;
                        }

                        if(grid[x][y]==1){
    
                            //假如遇到了另一座岛了，return level
                            return level;
                        }

                        if(grid[x][y]==0){
    
                            //假如遇到的还是0，那么就是下一层的0
                            points.push({
    x,y});
                            //这个0变为2
                            grid[x][y]=2;
                        }

                    }
                }
            }
        }
        return 0;
    }

    //辅函数
    void dfs(queue<pair<int,int>> &points,vector<vector<int>> &grid,
                int m,int n,int i,int j)
    {
    
        if(i<0||j<0||i==m||j==n||grid[i][j]==2){
    
            return;
        }

        if(grid[i][j]==0){
    
            points.push({
    i,j});
            return;
        }

        grid[i][j]=2;
        dfs(points,grid,m,n,i-1,j);
        dfs(points,grid,m,n,i+1,j);
        dfs(points,grid,m,n,i,j-1);
        dfs(points,grid,m,n,i,j+1);
    }
};