宽度优先搜索（BFS）算法之一——最短路径
2.1 马的遍历 P1443
有一个 的棋盘，在某个点 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
输入数据格式
输入只有一行四个整数，分别为 。
输出数据格式
一个 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 ）。
输入输出样例
| 输入 #1 | 输出 #1 |
|---|---|
| 3 3 1 1 | 0 3 2 3 -1 1 2 1 4 |
说明与提示
数据规模与约定
对于全部的测试点，保证 ，。
参考代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int vis[405][405]; //方格
struct Tnode{ //队列
int x,y;
} qu[405*405];
int dx[8]={-1,-2,-2,-1,1,2,2,1};
int dy[8]={2,1,-1,-2,2,1,-1,-2};//8个方向
void bfs(int x0, int y0) {
int head=0,tail=0; //队列的头和尾
qu[0].x = x0; //开始位置进队列
qu[0].y = y0;
tail++;
vis[x0][y0]=0; //记录到x，y的步数，同时也充当探索标记（=-1 表示没有探索过）
int ans=0;
while (head<tail){//队列非空
int x = qu[head].x; //取队列的头
int y = qu[head].y;
head++; //出队列
int step = vis[x][y]; //父节点到x,y所需要的步数
for (int d=0; d<8; d++) {
int nx=x+dx[d]; //四周坐标
int ny=y+dy[d];
if (nx>=1 && nx<=n && ny>=1 && ny<=m && vis[nx][ny]==-1){ //可以进入
vis[nx][ny]=step+1;
qu[tail].x = nx; //进队列
qu[tail++].y = ny;
}
}
}
return;
}
int main(){
int x,y;
cin >> n >> m >> x>>y;
//for(int i=1;i<=n;i++)
// for(int j=1;j<=m;j++)
// vis[i][j]=-1;
memset(vis,0xff,sizeof(vis));
bfs(x,y);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cout<<vis[i][j]<<" ";
cout<<"\n";
}
return 0;
}
2.2 离开中山路 P1746
爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在 处，车站在 处。现在给出一个 的地图， 表示马路， 表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱 与愁大神为了节省时间，他要求最短到达目的地距离（每两个相邻坐标间距离为 ）。你能帮他解决吗？
输入数据格式
第 行包含一个数 。
第 行到第 行：整个地图描述（ 表示马路， 表示店铺，注意两个数之间没有空格）。
第 行：四个数 。
输出数据格式
只有 行，即最短到达目的地距离。
输入输出样例
| 输入 #1 | 输出 #1 |
|---|---|
| 3 001 101 100 1 1 3 3 | 4 |
说明与提示
对于 数据，满足 。
对于 数据，满足 。
参考代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
string vis[1005]; //方格
int step[1000][1000];
struct Tnode{ //队列
int x,y;
} qu[1000005];
int dx[4]={-1,0,+1,0};
int dy[4]={0,+1,0,-1};//4个方向
void bfs(int x0, int y0) {
int head=0,tail=0; //队列的头和尾
qu[0].x = x0; //开始位置进队列
qu[0].y = y0;
tail++;
vis[x0][y0]=0; //记录到x，y的步数，同时也充当探索标记（=-1 表示没有探索过）
int ans=0;
while (head<tail){//队列非空
int x = qu[head].x; //取队列的头
int y = qu[head].y;
head++; //出队列
for (int d=0; d<4; d++) {
int nx=x+dx[d]; //四周坐标
int ny=y+dy[d];
if (nx>=0 && nx<n && ny>=0 && ny<n&&vis[nx][ny]=='0'){ //可以进入
vis[nx][ny]='2';
step[nx][ny]=step[x][y]+1;
cout<<nx<<"-"<<ny<<endl;
qu[tail].x = nx; //进队列
qu[tail++].y = ny;
}
}
}
return;
}
int main(){
cin>>n;
for(int i=0;i<n;i++)
cin>>vis[i];
//memset(vis,0xff,sizeof(vis));
int x,y,x2,y2;
cin >> x >> y >> x2>>y2;
bfs(x-1,y-1);
cout<<step[x2-1][y2-1];
return 0;
}
2.3 岛屿的最大面积
给定一个由 0 和 1 组成的n*m矩阵 ，用来表示海洋岛屿地图。一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 矩阵的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
例如：
输出的结果是：
6
输入格式
第一行2个正整数n和m,范围[4，1000]。 下面 n行每个行 m个数，都是0或1。
输出格式
1个整数，答案。
输入/输出例子1
输入：
3 3
0 0 1
1 1 0
1 1 1
输出：
5
参考代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1002][1002]; //方格
int ans=0;
struct Tnode{ //队列
int x,y;
} qu[1000000];
int dx[4] = { 0, 1, 0,-1}; //四个方向
int dy[4] = {-1, 0, 1, 0};
void BFS(int x0, int y0) {
qu[0].x = x0; //开始位置进队列
qu[0].y = y0;
a[x0][y0]=0;
int head=0; //队列的头和尾
int tail=1;
while (head<tail){//队列非空
int x = qu[head].x; //取队列的头
int y = qu[head].y;
head++; //出队列
for (int d=0; d<4; d++) {
int nx=x+dx[d]; //四周坐标
int ny=y+dy[d];
if (a[nx][ny]==1){ //可以
qu[tail].x = nx; //进队列
qu[tail++].y = ny;
a[nx][ny]=0; //访问过标记
}
}
}
if (tail>ans)
ans=tail;
}
int main(){
cin >> n >> m;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
cin >> a[i][j];
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if ( a[i][j]==1)
BFS(i,j);
cout << ans;
return 0;
}