bfs想必非常的熟悉了，bfs大多数用来解决什么问题呢？一个最直观经典的例子就是走迷宫，我们从起点开始，找出到终点的最短路程，很多最短路径算法就是基于广度优先的思想成立的。所以这篇博客，主要是利用bfs找迷宫的最短距离。首先看看bfs一般的使用套路：
Problem 2285 迷宫寻宝
链接：http://acm.fzu.edu.cn/problem.php?pid=2285
本题就是一个基本上就是纯模板题，就是从S开始走，走到终点E的路径最短，#是障碍物不能走，如果不能找到终点的路就输出-1，而且只能上下左右四个方向走。
思路就是先遍历一遍记录初始位置，和终点的位置，然后就是纯正的模板了，利用bfs来实现，但是在实现的过程中，如果找到终点那么就标记一下，然后break掉。没有标记的话就直接输入-1。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
char a[1010][1010];//记录整个图形的
int vis[1010][1010];//用来标记的走没走过
struct Point{
int x, y;
}tmp1, tmp2;
int mt[4][2] = {1,0,-1,0,0,1,0,-1};//移动的四个方向
queue<Point>q;
int main(){
int n, i, j;
while(~scanf("%d", &n)){
for(i = 0; i < n; i++){
scanf("%s", a[i]);
}
int sx, sy;
int ex, ey;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
vis[i][j] = 0;//初始化标记
if(a[i][j] == 'S'){//找到初始位置
sx = i;
sy = j;
}
else if(a[i][j] == 'E'){//终点位置
ex = i;
ey = j;
}
}
}
while(!q.empty()){//队列初始化
q.pop();
}
tmp1.x = sx;
tmp1.y = sy;
vis[tmp1.x][tmp1.y] = 1;//首先压入起始位置
q.push(tmp1);
int flag = 0;
while(!q.empty()){
tmp1 = q.front();
q.pop();
for(i = 0; i < 4; i++){
tmp2.x = tmp1.x + mt[i][0];//引动的方向
tmp2.y = tmp1.y + mt[i][1];
if(tmp2.x >=0 && tmp2.x < n && tmp2.y >= 0 && tmp2.y < n && !vis[tmp2.x][tmp2.y] && a[tmp2.x][tmp2.y] != '#'){
//判断条件
vis[tmp2.x][tmp2.y] = vis[tmp1.x][tmp1.y] + 1;//原来的位置加一
q.push(tmp2);
}
}
if(vis[ex][ey]){//如果到达终点就标记一下，表示能到达终点
flag = 1;
break;
}
}
if(flag)printf("%d\n", vis[ex][ey]-1);//终点位置也包括在内，所以减1
else printf("-1\n");
}
return 0;
}
移动
链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1181
本题就是在300*300的方格内移动问起始点到终止点的最小移动距离，输入数据只给了起始点坐标，和终止点坐标。本题也是一个非常明显的一个bfs题型。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
int vis[305][305];
int mt[8][2] = {1,2,2,1,2,-1,1,-2,-1,-2,-2,-1,-2,1,-1,2};
struct Point{
int x, y;
}tmp1, tmp2;
queue<Point>q;
int main(){
int sx, sy, ex, ey;
while(~scanf("%d %d %d %d", &sx, &sy, &ex, &ey)){
while(!q.empty()){
q.pop();
}
memset(vis, 0, sizeof(vis));//注意格式化，切记。非常容易忘
tmp1.x = sx;
tmp1.y = sy;
vis[tmp1.x][tmp1.y] = 1;
q.push(tmp1);
int i;
while(!q.empty()){
tmp1 = q.front();
q.pop();
for(i = 0; i < 8; i++){
tmp2.x = tmp1.x + mt[i][0];
tmp2.y = tmp1.y + mt[i][1];
if(tmp2.x >= 0 && tmp2.x <=300 && tmp2.y >= 0 && tmp2.y <= 300 && !vis[tmp2.x][tmp2.y] ){
//判断条件范围限制在300*300的范围
vis[tmp2.x][tmp2.y] = vis[tmp1.x][tmp1.y] + 1;
q.push(tmp2);
}
}
if(vis[ex][ey])break;
}
printf("%d\n", vis[ex][ey]-1);
}
return 0;
}
迷宫问题
链接：http://poj.org/problem?id=3984
本题也是一个走迷宫的问题，但是本题和之前的几道题之间的差距就在于本题问你是如何走得，也就时你走迷宫的具体路径，主体思想跟之前的几道题没有变依然是bfs类的问题，但是重点是如何储存走过的点，以及如何输出。
记录输入输出的思想就是要从终点开始往回找点，用另外的结构体数组储存一下，然后输出就可以了，但是如何往回找呢？往回找就看你是如何储存的，先申请结构体数组。用要压入点的位置pre[tmp2.x][tmp2.y].x来记录前一个数组横坐标的位置，pre[tmp2.x][tmp2.y].y来记录另外一个数字纵坐标的位置。
pre[tmp2.x][tmp2.y].x = tmp1.x;
pre[tmp2.x][tmp2.y].y = tmp1.y;
#include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int maze[6][6];
int vis[6][6];
struct Point{
int x, y;
}tmp1, tmp2;
Point pre[10][10];
int mt[4][2] = {1,0,-1,0,0,1,0,-1};
queue<Point>q;
Point ans[30];
int main(){
int i, j;
while(~scanf("%d %d %d %d %d", &maze[0][0], &maze[0][1], &maze[0][2], &maze[0][3],&maze[0][4],&maze[0][5])){
for(i = 1; i < 5; i++){
for(j = 0; j < 5; j++){
scanf("%d", &maze[i][j]);
}
}
while(!q.empty()){
q.pop();
}
memset(vis, 0, sizeof(vis));
tmp1.x = 0;
tmp1.y = 0;
vis[0][0] = 1;
q.push(tmp1);
while(!q.empty()){
tmp1 = q.front();
q.pop();
for(i = 0; i < 4; i++){
tmp2.x = tmp1.x + mt[i][0];
tmp2.y = tmp1.y + mt[i][1];
if(tmp2.x >= 0 && tmp2.x < 5 && tmp2.y >= 0 && tmp2.y < 5 && !vis[tmp2.x][tmp2.y] && maze[tmp2.x][tmp2.y] == 0){
//约束条件
vis[tmp2.x][tmp2.y] = vis[tmp1.x][tmp1.y] + 1;
q.push(tmp2);
pre[tmp2.x][tmp2.y].x = tmp1.x;//保存前一个位置的横坐标
pre[tmp2.x][tmp2.y].y = tmp1.y;//保存前一个位置的纵坐标
}
}
if(vis[4][4])break;
}
//cout<<vis[4][4]<<endl;
int lastx = 4, lasty = 4;//终点的位置
int x, y, num = 0;
while(lastx || lasty){//如果lastx, lassty，如果全为零的话就停止
ans[num].x = lastx;//ans 来记录一下
ans[num++].y = lasty;
x = lastx;
y = lasty;
lastx = pre[x][y].x;//读取下一个，也就是之前保存的前一个
lasty = pre[x][y].y;
}
//cout<<num<<endl;
printf("(0, 0)\n");
for(i = num-1; i >= 0; i--){//逆序输出
printf("(%d, %d)\n", ans[i].x, ans[i].y);
}
}
return 0;
}