在给定的二维二进制数组a中，存在两个岛。 )岛是由四面相连的1构成的最大的组。 ）
现在，我们可以把0变成1，两个岛连接起来，成为一个岛。
返回必须反转的最小0数。 (我可以保证答案至少是1。 ）
示例 1：
输入： [ 0，1 ]，[ 1，0 ]输出：1 示例 2：
输入： [ 0，1，0 ]、[ 0，0，0 ]、[ 0，0，1 ]输出：2 示例 3：
输入： [ 1，1，1，1，1 ]、[ 1，0，0，1 ]、[ 1，0，0，1 ]、[ 1，0，0，1，1 ]
思路：主题指定只有两个岛，一开始没有连接。 请问至少要把几个0变成1才能联系上。 其实这是迷宫般的场面。 也就是说，给定两点，一个是起点，另一个是终点，询问到终点为止最低需要的步数。 这只是没有障碍物和墙壁。 转换为这个问题的话，就会求出从一个岛到另一个岛的最短距离。 为了区分这两个岛，可以把一个岛的数字1都定为数字2，另一个岛保持不变。 题意变换为从所有数字都由1构成的岛到所有数字都由2构成的岛的最短距离。
将实例3作为示范：
第一个岛是这样的
一，一，一，一，一
1，0，0，0，1
1，0，1，0，1
1，0，0，0，1
一，一，一，一，一
现在我把第一个岛上的所有数字都变成2
二，二，二，二，二
2，0，0，0，2
2，0，1，0，2
2，0，0，0，2
二，二，二，二，二
那么，求从中间数字为1的岛到数字为2的岛的最短距离吧。
所以总结起来也就两步。 一、把岛上所有的数字都变成2。 (这里利用深度搜索。 二、求出数字1的岛到数字2的岛的距离(也可以求出数字2的岛到数字1的岛的距离，这里利用广搜索。
直接访问代码，具体做法看注释
class solution { public : intshortestbridge (vectorvectorinta )//旧规则首先必须是二维数组为空的if(a.empty )||A[0].empty //m是行数，n是列数int i，j； vectorvectorintmove={ 1，0 }、{0，1 }、{-1，0 }、{ 0，-1}； //用于在四个方向上广泛搜索bool flag=false； //执行第一步，将岛上的一个数字都设为2for(I=0)的im； I ) for(j=0； jn； j () if ) a[I][j]==1)//遇到岛) { flag=true； DFS(a，I，j，m，n )； //深渔将第一个岛的1全部改为2 break； ()把一个岛的数字都定为2，然后直接退出循环。 因为不需要将另一个岛分成2 ) if(flag ) break； //首先在回答中设置无穷大值int res=0x3f3f3f3f的for(I=0； im； I ) for(j=0； jn； j ) if(a[I][j]==1)//要找到另一个岛，必须全面搜索该岛的每个点(寻找到数字2岛的距离)。 在这些点中，与其他岛的最短距离是答案({ //state数组用于记录步数。 将一个点进一步记录为vectorveeer最初以步数1 (记住，这是关键) state[i][j]=1； res=
min(res,bfs(A,move,state,i,j)); } } } return res; } bool bound(int i,int j,int m,int n) //越界情况返回true，再广搜的时候用到 { if(i<0||j<0||i>=m||j>=n) return true; return false; } //把岛中的数字1全部变成2 void dfs(vector<vector<int>>& A,int i,int j,int m,int n) { if(i<0||j<0||i>=m||j>=n) //越界退出 return; if(A[i][j] == 1) //凡是遇到1就变成2 { A[i][j] = 2; //深度扩散 dfs(A,i+1,j,m,n); dfs(A,i-1,j,m,n); dfs(A,i,j+1,m,n); dfs(A,i,j-1,m,n); } } //求点A(i,j)到值为2的坐标点的最短距离 int bfs(vector<vector<int>>& A,vector<vector<int>>& move,vector<vector<int>>& state,int i,int j) { int m = A.size(),n = A[0].size(); queue<pair<int,int>> q; //创建一个队列记录我们即将走的坐标点 q.push({i,j}); //一开始我们是在(i,j)这个坐标点出发的，记录进队列中 while(!q.empty()) { pair<int,int> p = q.front();q.pop(); if(A[p.first][p.second] == 2) //当来到了数字全为2的岛上时，可以返回步数-2，-2是因为我们走多了两步，一步是起始的位置，另一步是终点的位置。实际上这两步是不需要计算进去的 return state[p.first][p.second]-2; //利用move数组，以当前位置为中心向四周走 for(int i = 0;i<4;i++) { //(px,py)为下一个要走的坐标点 int px = p.first+move[i][0],py = p.second+move[i][1]; //当越界了就跳到下一个循环 if(bound(px,py,m,n)) continue; //当我们之前曾经来过当前点或者当前点为自己原本的岛的时候，跳到下一个循环 if(state[px][py]||A[px][py] == 1) continue; //把下次要走的坐标记录进队列中 state[px][py] = state[p.first][p.second]+1; q.push({px,py}); } } return 0x3f3f3f3f; }};