Leetcode-934: the shortest Bridge

subject

Topic linking

In a given two-dimensional binary array A in , There are two islands .（ The island is connected by four sides 1 Form a largest group .）

Now? , We can 0 Turn into 1, To connect the two islands , Become an island .

Returns the that must be flipped 0 The minimum number of .（ You can guarantee that the answer is at least 1 .）

Example 1：

 Input ：A = [[0,1],[1,0]]
 Output ：1

Example 2：

 Input ：A = [[0,1,0],[0,0,0],[0,0,1]]
 Output ：2

Example 3：

 Input ：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]]
 Output ：1

Problem solving

Method 1 ：BFS

1. First traverse , Find a point on one of the islands
2. Mark all the islands found in the first step as -1
3. Starting from the first island , Start BFS, But when I met 1, It means we met the second island

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();
        // Find the point of one of the islands 
        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
        // Mark one of the found islands as -1, And save it all q2 in 
        queue<pair<int,int>> q1;// be used for bfs
        queue<pair<int,int>> q2;// Save the node , For the following bfs Initial value 
        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 Indicates the points that have been visited ,0 Indicates points that have not been visited ,1 Indicates the destination Island 
        // Find the value for 1 The dot of indicates that you have found 
        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;

    }
};