迷宫问题(BFS问题) - POJ 3984
本题是新加入我们的大虾Gabriel童鞋写的，他是一个刚入大学的大一新生，孺子如虎也，赞！
Description
定义一个二维数组：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
关于BFS算法：
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
解题思路：
该题目是找寻最短路径，要想做出这道题，只需要解决2个问题：
1）找到一条最短路；
2）打印出来。
当然从起点到终点有不止一条路，找到一条最短路就是我们主要需要解决的问题
怎样才算最短的呢？也就是步数最少的，那么我们就可以用BFS搜索解决。
BFS搜索的基本思路为：
按步数搜索，也就是我们从起点开始，找到这个点的所有可能走到的点，这些点就为走一步能到的点。
然后再把所有的走一步能走到的点，再寻找它下一步能走到的点，一直循环重复直到找到终点，那就是从起点能到终点的最短路径了，然后再把每一步的路径存储，搜索完过后打印出来，就能解决问题了。
源码：G++
#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
// 定义的一个结构体w，x和y表示一个点的坐标
typedef struct point_s
{
int x;
int y;
} point_t;
/* 定义一个结构体二维数组
father[x][y].x存的是最短路径的坐标为（x，y）点的下一个坐标的横坐标x
father[x][y].y存的是最短路径的坐标为（x，y）点的下一个坐标的纵坐标y */
point_t father[6][6];
//一个5X5的二维数组表示地图
int maze[5][5];
/* 因为是找最短的路径，所以之前走过的路不能再走，当visited[X][Y]=0时，
表示之前没走过（x，y）这个点，同理，为1时，表示走过 */
int visited[6][6];
/*每一个点能走上下左右4个方向
move[1][0]表示向下走时x坐标该加的值（x+1）
move[1][1]表示向下走时y坐标该加的值（y不变）
move[2][0],move[2][1]表示向右走时，x和y对应的坐标变化
*/
int move[4][2] = {1, 0, 0, 1, 0, -1, -1, 0};
int check(int x, int y) //定义一个检查函数，来检查能不能走到（x，y）这个点，能返回1，不能返回0；
{
/* 能走到这个点满足的条件有
1：该点没被走过，对应的代码是 visited[x][y]==0
2：该点不是墙，是路，对应的代码是 maze[x][y]==0
3：该点 属于5X5的这个迷宫内部，对应的代码是 x<=4&&y<=4&&x>=0&&y>=0
*/
if (visited[x][y] == 0 && maze[x][y] == 0 && x <= 4
&& y <= 4 && x >= 0 && y >= 0) {
//当以下3点满足时，返回1，表示能走到这个点
return 1;
}
//如果前面没有return，代表不能走到这个点，于是返回0
return 0;
}
//主要的BFS搜索函数
void bfs()
{
//定义2个w结构体，point1表示第一个点，point2表示由point1这个点走到的一个点
point_t point1, point2;
//我们选择从右下角忘前面搜，搜到左上角就结束，所以第一个点为（4，4）
point1.x = 4;
point1.y = 4;
//定义一个结构体队列q
queue<point_t> q;
//将第一个点（4，4）加入队列
q.push(point1);
// 当这个队列没空时，就一直循环
while (!q.empty())
{
//取出队列的首端并赋值给point1结构体
point1 = q.front();
//删除队列的首端元素
q.pop();
//当point1为（0，0）时，说明找到了出口，函数结束
if (point1.x == 0 && point1.y == 0)
break;
// 临时变量
int i, tmp_x, tmp_y;
//因为一个点可能能走4步，所以i从0到3，4次循环
for (i = 0; i < 4; i++)
{
tmp_x = point1.x + move[i][0];
//（tmp_x，tmp_y）表示由point1这个点可能 能够走到的所有点
tmp_y = point1.y + move[i][1];
//检查（tmp_x，tmp_y）这个点到底能不能走到，上面有check函数的解释
if (check(tmp_x, tmp_y))
{
//把（tmp_x，tmp_y）这个点赋给point2
point2.x = tmp_x;
point2.y = tmp_y;
//更新father结构体数组中的数据，该数组的意义上面有解释
father[point2.x][point2.y].x = point1.x;
father[point2.x][point2.y].y = point1.y;
//把point2这个点赋为1，表示走过该点
visited[point2.x][point2.y] = 1;
//把point2这个点放进队列中
q.push(point2);
}
}
}
}
//打印答案的函数
void printf()
{
//起点为（0，0）
int x = 0, y = 0;
//当坐标不为（4，4）时，也就是当没走到右下角时，一直循环
while (!(x == 4 && y == 4))
{
//打印该点坐标，最开始打印（0，0）
printf("(%d, %d)\n", x, y);
//tmp_x，tmp_y表示最短路径时（x，y）这个点的下一个点的坐标
int tmp_x, tmp_y;
//赋值给tmp_x，tmp_y
tmp_x = father[x][y].x;
tmp_y = father[x][y].y;
//现在的（x，y）就是这个循环中打印的那个（x，y）的走到的下一个点坐标
x = tmp_x;
y = tmp_y;
}
// 当（x，y）为（4，4）时退出循环，
//当然也要打印最后一个点
printf("(%d, %d)\n", x, y);
}
int main()
{
int i, j;
//输入迷宫maze
for (i = 0; i < 5; i++)
{
for (j = 0; j < 5; j++)
scanf("%d", &maze[i][j]);
}
// 将visited数组全部赋值为0，表示最开始都没走过
for (i = 0; i < 6; i++)
{
for (j = 0; j < 6; j++)
visited[i][j] = 0;
}
//搜索
bfs();
//打印答案
printf();
return 0;
}