题目
给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
返回必须翻转的 0 的最小数目。
示例 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].length2 <= n <= 100grid[i][j]为0或1grid中恰有两个岛
思路
第一次广搜：先对矩阵进行遍历，找出第一座岛的一个陆地单元格，并将他作为广搜的起始点。把起始点添加到队列中，同时将他标记为-1表示已访问，然后从队列中取出元素，对上下左右四个相邻单元格进行检查。如果相邻单元格处于矩阵范围内且为陆地，就标记为-1并加入队列。持续这个过程，直到队列为空，把第一座岛的所有陆地单元格都标记为-1。
第二次广搜：把所有标记为-1的陆地单元格添加到队列中，当作第二次广搜的起点。同时，把sum初始化为-1。最后队列中取出元素，对上下左右四个相邻单元格进行检查，如果相邻单元格处于矩阵范围内且为第二座岛的陆地，则说明已找到第二座岛，返回sum+1。如果相邻单元格处于矩阵范围内且为水域，就将他标记为-1并加入队列。每完成一层的扩展，就把sum的值加1。
代码
class Solution {
public://用于上下左右移动int di[4]={-1,0,1,0};int dj[4]={0,-1,0,1};int shortestBridge(vector<vector<int>>& grid) {//用于bfs的队列queue<pair<int,int>>res;//获取网格的大小int n=grid.size(),a,b;// 找到第一座岛的一个陆地单元格for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){a=i;b=j;}}}//将陆地单元格加入队列res.push({a,b});//标记单元格为 -1，表示已访问grid[a][b]=-1;//用于记录翻转的0的数量,初始化为-1int sum=-1;//确保在计算需要翻转的0的数量时，不会把起点的陆地单元格计算在内//第一次bfs，标记第一座岛的所有陆地单元格为-1while(!res.empty()){auto z=res.front();//提取队列中第一个元素res.pop();//移除队首元素for(int i=0;i<4;i++){int x=z.first+di[i],y=z.second+dj[i];//分别是横坐标和纵坐标//检查新位置是否在网格内且为陆地if(x>=0&&x<n&&y>=0&&y<n&&grid[x][y]==1){//标记为 -1grid[x][y]=-1;//加入队列res.push({x,y});}}}//将标记为-1的所有陆地单元格加入队列，作为第二次bfs的起点for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(grid[i][j]==-1){res.push({i,j});}}}//第二次bfs，向外扩展直到碰到另一座岛while(!res.empty()){//当前层的单元格数量int s=res.size();while(s--){ auto z=res.front();res.pop();for(int i=0;i<4;i++){int x=z.first+di[i],y=z.second+dj[i];//检查新位置是否在网格内并且是另一座岛的陆地if(x>=0&&x<n&&y>=0&&y<n&&grid[x][y]==1){//找到另一座岛，返回翻转的 0 的数量return sum+1;}//检查新位置是否在网格内且为水域if(x>=0&&x<n&&y>=0&&y<n&&grid[x][y]==0){//标记为 -1grid[x][y]=-1;//加入队列res.push({x,y});}}}//扩展一层，翻转的0的数量加 1sum++;}return sum;}
};
