广度优先搜索 | 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

二、题解

这道题用到了DFS和BFS。
DFS应用在寻找“岛屿”的时候，通过递归将一个连通的区域作为一个岛，同时在递归寻找岛的时候，除了将访问过的陆地进行标记外，也将“河流”所属的区域坐标保存到队列中。
BFS用于从河流覆盖的坐标出发，寻找周围（上下左右）是否为陆地。

三、代码

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

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

       //bfs寻找第二个岛屿，并把0赋值为2
       int x,y;
       int level=0;
       while(!points.empty()){
           ++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&&y>=0&&x<m&&y<n){
                   if(grid[x][y]==2){
                       continue;
                   }
                   if(grid[x][y]==1){
                       return level;
                   }
                    points.push({x,y});
                    grid[x][y]=2;                 
               }
           }
       }
    }     

       return 0;//说明Points是空的
}

    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);
    }
};
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