题目
在给定的二维二进制数组 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
解题
方法一：BFS
1.首先遍历，找到其中岛屿的一个点
2.将第一步中找到的那个岛屿全部标记成-1
3.从第一个岛屿出发，开始BFS(层序遍历)，一但遇到1，就说明遇到第二个岛屿了
class Solution { public: vector<vector<int>> dirs={{-1,0},{1,0},{0,1},{0,-1}}; int shortestBridge(vector<vector<int>>& grid) { int m=grid.size(); int n=grid[0].size(); //找到其中一个岛屿的点 pair<int,int> startPoint; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]==1){ startPoint={i,j}; goto OUT; } } } OUT: //BFS //将找到的其中一个岛屿全部标记成-1，并把它全部存入q2中 queue<pair<int,int>> q1;//用于bfs queue<pair<int,int>> q2;//将节点存起来，用于之后的bfs初始值 grid[startPoint.first][startPoint.second]=-1; q1.push(startPoint); while(!q1.empty()){ auto [x,y]=q1.front(); q2.push({x,y}); q1.pop(); for(vector<int>& dir:dirs){ int nx=x+dir[0]; int ny=y+dir[1]; if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]==1){ q1.push({nx,ny}); grid[nx][ny]=-1; } } } //BFS //-1表示已经访问过的点，0表示还未访问过的点，1表示目的岛屿 //找到值为1的点就说明找到了 int count=0; while(!q2.empty()){ int l=q2.size(); for(int i=0;i<l;i++){ auto [x,y]=q2.front(); q2.pop(); for(vector<int>& dir:dirs){ int nx=x+dir[0]; int ny=y+dir[1]; if(nx>=0&&nx<m&&ny>=0&&ny<n){ if(grid[nx][ny]==1) return count; else if(grid[nx][ny]==0){ q2.push({nx,ny}); grid[nx][ny]=-1; } } } } count++; } return -1; } };
