一、题面
在给定的二维二进制数组 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,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1
提示：
1 <= A.length = A[0].length <= 100A[i][j] == 0或A[i][j] == 1
二、分析
首先需要用dfs对一个连通块进行标记，然后对其中一个连通块进行bfs搜索，直到第一次触碰到另外一个连通块，即最少的反转次数。
三、代码
class Solution {
public:
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int N, M;
void dfs(int x, int y, vector<vector<int>>& A, vector<pair<int, int> >& B)
{
int nx, ny;
A[x][y] = 2;
B.push_back(make_pair(x, y));
for(int i = 0; i < 4; i++)
{
nx = x + dx[i];
ny = y + dy[i];
if(nx>=0 && nx < N && ny>=0 && ny < M && A[nx][ny]==1 )
{
dfs(nx, ny, A, B);
}
}
}
int Min(int a, int b)
{
return a<b?a:b;
}
int Abs(int a)
{
if(a < 0)
return -a;
return a;
}
int shortestBridge(vector<vector<int>>& A) {
int ans = 0;
vector<pair<int, int> > B;
N = A.size(), M = A[0].size();
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
if(A[i][j]==1)
{
dfs(i, j, A, B);
i = N;
break;
}
}
}
/*for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
cout<<A[i][j]<<" ";
}
cout << endl;
}*/
queue<pair<int, int> > Q;
for(int i = 0; i < B.size(); i++)
{
Q.push(B[i]);
}
while(!Q.empty())
{
int Size = Q.size();
while(Size>0)
{
pair<int, int> top = Q.front();
Q.pop();
for(int i = 0; i < 4; i++)
{
int x = top.first + dx[i];
int y = top.second + dy[i];
if(x>=0 && x < N && y>=0 && y < M && A[x][y]==1)
{
return ans;
}
else if(x>=0 && x < N && y>=0 && y < M && A[x][y]==0)
{
A[x][y] = 2;
Q.push(make_pair(x, y));
}
}
Size--;
}
ans++;
}
return ans;
}
};