迷宫问题：
定义一个二维数组：
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
左上角到右下角的最短路径，格式如样例所示。
这题就一组数据，可以说水得不能再水了。直接输出样例的答案就能过了。
但是认真想：这题要输出路径，也就是记录你走过的点，感觉还是有点难度的
我使用的方法是用数组来广搜而不是常用的队列。
数组相比队列，删除操作时间复杂度很高，因此广搜采用的数据结构一般为队列。但是这道题要记录走过的点，数组的优势就凸显出来了——即访问效率高，而队列则是限制存取点的数据结构，相比之下这道题用数组就合适的多了。
代码详解：
首先还是构造结构体，与平常不同的是多了一个变量pre，用以记录当前点的上一个点在数组中的下标。
typedef struct{int pre; //标记上一个点int x;int y;
}pos;pos p[100];
int maze[10][10];
int vis[10][10];
int direct[4][2]={
{1,0},{-1,0},{0,-1},{0,1}};
int cnt=1;数组实现广搜：
pos bfs(){p[0].pre=-1; p[0].x=0;p[0].y=0; //初始点（0，0）vis[1][1]=1;for(int i=0;;i++){for(int j=0;j<4;j++){ //四个方向搜索int tempx=p[i].x+direct[j][0];int tempy=p[i].y+direct[j][1];if(tempx>=0&&tempx<=4&&tempy>=0&&tempy<=4&&maze[tempx][tempy]!=1&&!vis[tempx][tempy]){vis[tempx][tempy]=1;p[cnt].pre=i; //记住当前点的上一个点在p数组中的位置p[cnt].x=tempx;p[cnt].y=tempy;cnt++;if(tempx==4&&tempy==4){return p[cnt-1];}}}}
}回溯输出：
void dfs(pos now){if(now.x==0&&now.y==0){printf("(%d, %d)\n",now.x,now.y);return ;}dfs(p[now.pre]);printf("(%d, %d)\n",now.x,now.y);
}
AC代码：
#include <cstdio>
#include <queue>
#include <string.h>
#include <iostream>
using namespace std;typedef struct{int pre; //标记上一个点int x;int y;
}pos;int maze[10][10];
int vis[10][10];
int direct[4][2]={
{1,0},{-1,0},{0,-1},{0,1}};
pos p[100]; //
int cnt=1;pos bfs(){p[0].pre=-1;p[0].x=0;p[0].y=0;vis[1][1]=1;for(int i=0;;i++){for(int j=0;j<4;j++){int tempx=p[i].x+direct[j][0];int tempy=p[i].y+direct[j][1];if(tempx>=0&&tempx<=4&&tempy>=0&&tempy<=4&&maze[tempx][tempy]!=1&&!vis[tempx][tempy]){vis[tempx][tempy]=1;p[cnt].pre=i;p[cnt].x=tempx;p[cnt].y=tempy;cnt++;if(tempx==4&&tempy==4){return p[cnt-1];}}}}
}void dfs(pos now){if(now.x==0&&now.y==0){printf("(%d, %d)\n",now.x,now.y);return ;}dfs(p[now.pre]);printf("(%d, %d)\n",now.x,now.y);
}int main()
{memset(vis,0,sizeof(vis));for(int i=0;i<5;i++)for(int j=0;j<5;j++)scanf("%d",&maze[i][j]);pos end_point=bfs();dfs(end_point);return 0;
}