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

本文主要是介绍广度优先搜索 | 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赋值为2bool 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赋值为2int 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);}
};