在一个NxN的布尔矩阵中，0表示水，1表示陆地，一片由1围成的最大区域就是一个岛，假定方阵中有且只有两个岛，请计算连接这两个岛的最短的桥的长度（架桥相当于翻转0为1，使两个岛相连）。
输入样例1:
第一行一个正整数N（取值范围在[2--100]）。 以后N行以空格分隔的0或1，每行N个（0表示水，1表示陆地）。
3
0 0 1
0 0 1
1 1 0输出样例1:
一个表示最短的桥的长度的正整数，本例中，正中间或右下角均是可行方案。
1输入样例2:
第一行一个正整数N（取值范围在[2--100]）。 以后N行以空格分隔的0或1，每行N个（0表示水，1表示陆地）。
5
1 1 1 1 1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 1输出样例2:
一个表示最短的桥的长度的正整数，本例中，最后一行是可行方案。
3思路：
首先我们要做到区分两个岛，那怎么区分呢？
通过连通块，因为两个岛都被标记成了1，但两个岛分别属于两个不同的连通块，所以我们可以通过求解连通块去将其中一个岛的标记从1修改为其他的数字(这里我修改成了2)
求连通块，BFS，DFS都行，这里我用DFS，代码会简洁一些
void dfs(int x , int y) //从一个岛的任意一点出发
{
G[x][y] = 2; //每到一个点都把自身标记为2
for(int i = 0 ; i < 4 ; i++) //再向上下左右四个方向去拓展
{
int tx = x + dx[i][0] , ty = y + dx[i][1];
if(tx >= 0 && tx < n && ty >= 0 && ty < n && G[tx][ty] == 1) //保证不越界，并且是岛内的点
dfs(tx , ty);
}
}标记完连通块，剩下就是求两个连通块的最短路径了
我们先看问题的类型，由于都是连通块，所以，起点和终点都是有一个或多个的
那么类型就属于多源最短路
那么很容易想到Floyd算法，我们再看复杂度，n<=100，1s最多执行~
，那么我们最多可以使用
，而Floyd算法的复杂度是
是可行的
但是Floyd算法是需要有边的存在的，而这道题没有边，但是两点之间的距离也很简单能过算出，比如有两个点A，B，A点的坐标是(x1 , y1)，B点的坐标是(x2 , y2)
那么AB两点的距离
我们可以通过枚举两个岛上的点的坐标计算两点之间的最短距离，每次计算取最小值，最后就是两个岛的最短距离了
int ans = 210; //初始化答案为最大距离
for(int a = 0 ; a < n ; a++)
{
for(int b = 0 ; b < n ; b++)
{
for(int c = 0 ; c < n ; c++)
{
for(int d = 0 ; d < n ; d++) //通过四层循环来枚举两个点的坐标A(a,b),B(c,d)
{
if(G[a][b] + G[c][d] == 3) //判断两个点是否来自两个岛，只有2 + 1才能得到3
ans = min(ans , abs(a - c) + abs(b - d) - 1);//每次和最终答案取最小值
}
}
}
}同样，这题也可以通过多源BFS来做，多源BFS和普通的BFS差别就在，多源BFS初始队列有一个或多个元素，而普通BFS初始队列仅有一个元素(可以理解为多源BFS是有一个超级源点，该超级源点到某些点的距离为0，那么BFS一次就会把这些点都入队)
我们可以在求解连通块的同时，把同一个岛的点都入队
然后再进行BFS拓展，第一次拓展到其他岛的点所消耗的步数就是两个岛的最短距离
int bfs()
{
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0 ; i < 4 ; i++)
{
int tx = t.x + dx[i][0] , ty = t.y + dx[i][1];
if(tx >= 0 && tx < n && ty >= 0 && ty < n && G[tx][ty] != -1)
{
if(G[tx][ty] == 1) //第一次拓展到其他岛上的点就返回所花费的步数
return t.step;
G[tx][ty] = -1; //将该点标记为-1，表示为已经访问，防止重复访问
q.push({tx , ty , t.step + 1});
}
}
}
}代码一(类Floyd算法)：
//L3-1 桥短几何 (30 分)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 210;
int n;
int x , y;
int G[N][N];
int dx[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
void dfs(int x , int y)
{
G[x][y] = 2;
q.push({x , y , 0});
for(int i = 0 ; i < 4 ; i++)
{
int tx = x + dx[i][0] , ty = y + dx[i][1];
if(tx >= 0 && tx < n && ty >= 0 && ty < n && G[tx][ty] == 1)
dfs(tx , ty);
}
}
int main()
{
cin>>n;
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n ; j++)
{
cin>>G[i][j];
if(G[i][j])
x = i , y = j;
}
}
dfs(x , y);
int ans = 210;
for(int a = 0 ; a < n ; a++)
{
for(int b = 0 ; b < n ; b++)
{
for(int c = 0 ; c < n ; c++)
{
for(int d = 0 ; d < n ; d++)
{
if(G[a][b] + G[c][d] == 3)
ans = min(ans , abs(a - c) + abs(b - d) - 1);
}
}
}
}
cout<<ans;
return 0;
}代码二(多源BFS)：
//L3-1 桥短几何 (30 分)
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 210;
struct Point
{
int x;
int y;
int step;
};
int n;
int x , y;
int G[N][N];
queue<Point> q;
int dx[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
void dfs(int x , int y)
{
G[x][y] = 2;
q.push({x , y , 0});
for(int i = 0 ; i < 4 ; i++)
{
int tx = x + dx[i][0] , ty = y + dx[i][1];
if(tx >= 0 && tx < n && ty >= 0 && ty < n && G[tx][ty] == 1)
dfs(tx , ty);
}
}
int bfs()
{
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0 ; i < 4 ; i++)
{
int tx = t.x + dx[i][0] , ty = t.y + dx[i][1];
if(tx >= 0 && tx < n && ty >= 0 && ty < n && G[tx][ty] != -1)
{
if(G[tx][ty] == 1)
return t.step;
G[tx][ty] = -1;
q.push({tx , ty , t.step + 1});
}
}
}
}
int main()
{
cin>>n;
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n ; j++)
{
cin>>G[i][j];
if(G[i][j])
x = i , y = j;
}
}
dfs(x , y);
cout<<bfs();
return 0;
}