day66—BFS—最短的桥（LeetCode-934）

题目描述

给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。

岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。

你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。

返回必须翻转的 0 的最小数目。

输入格式

一个二维整数数组，输出是一个非负整数，表示需要填海造陆的位置数。
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]]

输出格式

一个整数代表答案。

示例 1：

输入：grid = [[0,1],[1,0]]
输出：1

示例 2：

输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
输出：2

示例 3：

输入：grid = [[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

提示：

• n == grid.length == grid[i].length
• 2 <= n <= 100
• grid[i][j] 为 0 或 1
• grid 中恰有两个岛

解决方案：

1、递归广度搜索部分：

终止条件：识别 0 则加入到队列中

单层递归：从该点的四个方向开始，一圈一圈的散射式搜索展开

2、主函数判断部分：

递归加入条件：遍历到 1 即加入循环判断周围有无 0

设置可变条件：bool filpped：是否可翻转

3、答案计数部分：

对于每层的循环加入的 0 位置点，周围是否存在 1 位置点可达并记录。

函数源码：

class Solution {
public:void bfs(queue<pair<int,int>>& points,vector<vector<int>>&grid,int row,int col,int i,int j){//越界条件判断if( i<0 || j<0 || i==row || j==col || grid[i][j]==2 )   return;//找到并记录 0 点位置if(grid[i][j]==0){points.push({i,j});return;}//降重，防止重复遍历grid[i][j]=2;//从该点的四个方向开始，一圈一圈的散射式搜索展开bfs(points,grid,row,col,i-1,j);bfs(points,grid,row,col,i+1,j);bfs(points,grid,row,col,i,j-1);bfs(points,grid,row,col,i,j+1);}//-------------------------------------------------------vector<int> direction{-1,0,1,0,-1};int shortestBridge(vector<vector<int>>& grid) {int row=grid.size();int col=grid[0].size();queue<pair<int,int>> points;bool flipped = false;   //flipped: 翻转for(int i=0;i<row;i++){if(flipped) break;for(int j=0;j<col;j++){if(grid[i][j]==1){bfs(points,grid,row,col,i,j);flipped=true;break;}}}
//-------------------------------------------------------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<row && y<col){if(grid[x][y]==2)   continue;if(grid[x][y]==1)   return level;points.push({x,y});grid[x][y]=2;}}}}return 0;}
};