Leetcode 934. Shortest Bridge

Posted on | In |

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Example 1:

Input: [[0,1],[1,0]]

Output: 1

Example 2:

Input: [[0,1,0],[0,0,0],[0,0,1]]

Output: 2

Example 3:

Input: [[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

Note:

1 <= A.length = A[0].length <= 100

A[i][j] == 0 or A[i][j] == 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
66
67
68
69
70
71
72

int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
class Solution {
public:
    int m,n;
     queue<pair<int,int>> q;
    vector<vector<int>> vec;
    int shortestBridge(vector<vector<int>>& A) {
       //先找到那个小岛再bfs;
       //(可能不止一个小岛)
       m=A.size();
        n=A[0].size();
        vec.swap(A);
        //  for(int i=0;i<m;i++){
        //     for(int j=0;j<n;j++)
        //        if(vec[i][j]) {
        //            dfs(i,j,q);
        //            break;
        //        }
        //      break;//!!只要找到一个连通分量就退出 错误 只遍历0这一行 没有1的话就break了
        // }
        bool flag=false;
                 for(int i=0;i<m&&!flag;i++){
            for(int j=0;j<n&&!flag;j++)
               if(vec[i][j]) {
                   dfs(i,j,q);
                  flag=true;
               }
         
        }
      //  cout<<q.size()<<endl<<endl;
        int steps=0;
        while(!q.empty()){
            int size=q.size();
            while(size--){
                
            
            pair<int,int> p=q.front();
            q.pop();
            int x=p.first;
            int y=p.second; 
           for(int i=0;i<4;i++){
            int newx=x+dir[i][0];
            int newy=y+dir[i][1];
            if(newx<0||newx>=m||newy<0||newy>=n||vec[newx][newy]==2) continue;
               
            if(vec[newx][newy]==1) {
                return steps;
            }
            vec[newx][newy]=2;
            q.push(pair<int,int>(newx,newy));//!!
            }
            
            }
           steps++;
        }
       
       return -1;
    }
   void dfs(int x,int y,queue<pair<int,int>>&q){
  
         if(x<0||x>=m||y<0||y>=n||vec[x][y]!=1) return;
         q.push(pair<int,int>(x,y));
     //  cout<<x<<" "<<y<<endl;
        vec[x][y]=2;
        for(int i=0;i<4;i++){
            int newx=x+dir[i][0];
            int newy=y+dir[i][1];
            dfs(newx,newy,q);
        }
    }
};