定义一个二维数组：
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; }
