题目链接：http://poj.org/problem?id=3984
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 0Sample Output
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)这道题是传统的迷宫搜索题，我感觉难办在路径的输出上，一开始试图开一个结构体记录。。。但后来发现。。。
迷宫搜索的两种方法：bfs和dfs，个人觉得bfs简单一点。。毕竟不用递归。。。因此就先试了试bfs的，dfs应该会更新。。应该会研究一下。。。
bfs篇：
好了，现在开一个结构体记录路径，用到了一个deque的容器，【然后每次记录路径，然后把这个路径存到一个队列中】这里非常重要！！是核心！！，用bfs解决。。。
不清楚deque的可以查一下或者看一下这个链接：
http://blog.csdn.net/qq_40482358/article/details/79335337
ok也可以看代码，代码我上面注释我感觉比较详细了。。。。
ac：代码有点长。。但大部分都是头文件。。遇到个新的就加上去。。已经这么多了啊。。
#include<stdio.h> #include<string.h> #include<math.h> //#include<map> //这里map会冲突。。。 #include<deque> #include<queue> #include<stack> #include<string> #include<iostream> #include<algorithm> using namespace std; #define ll long long #define da 0x3f3f3f3f #define xiao -0x3f3f3f3f #define clean(a,b) memset(a,b,sizeof(a))// 雷打不动的头文件 //尝试bfs路径。。 struct dop{ //坐标（点） int x,y; }; struct rode{ //路径 deque<dop> r; //路径队列 （点的集合） }; int fx[4]={0,0,-1,1},fy[4]={-1,1,0,0};//方向 int map[10][10]; //地图 int biaoji[10][10]; //是否走过 int l[10][10]; //路径长度 int main() { clean(biaoji,0); //初始化 clean(map,0); int i,j,k=0; for(i=0;i<5;++i) { for(j=0;j<5;++j) cin>>map[i][j]; //输入地图 } dop a; //初始点（起点） a.x=0; a.y=0; biaoji[0][0]=1; //起点标记 rode r; r.r.push_back(a); //起点加入路径 queue<rode> q; //一个路径的队列 q.push(r); //路径入列 while(q.size()) //存在路径 { rode nr=q.front(); //提取第一个路径 dop nd=nr.r.back(); //现在的点（位置） //输出最终的路径 if(nd.x==4&&nd.y==4) //如果到了目标点 { //printf("%d\n",l[4][4]);//这个是我看路径长度的。。题上没有要求。。 while(nr.r.size()) //如果该队列的点（路径）仍存在 { dop cand; //定义该点 cand=nr.r.front(); //该点是队首元素（点） printf("(%d, %d)\n",cand.x,cand.y);//输出 注意中间有个空格！！！wa了几次。。。 nr.r.pop_front(); //将队首元素释放 } return 0; } q.pop(); // 将该路径的释放 for(i=0;i<4;++i) //四个方向移动 { rode canr=nr; //避免对一开始的路径影响（加入条参数路径） int nx=nd.x+fx[i],ny=nd.y+fy[i];//向四周移动 if(nx>=0&&nx<5&&ny>=0&&ny<5) //在地图上 { if(map[nx][ny]!=1&&biaoji[nx][ny]==0)//不是墙&&没走过 { dop cand; //定义一个点 cand.x=nx; //x坐标 cand.y=ny; //y坐标 canr.r.push_back(cand);//将这个点放入现在这个路径的，路径（点）中 q.push(canr); //将这个路径加入队列 biaoji[nx][ny]=1;//标记该点走过了 l[nx][ny]=l[nd.x][nd.y]+1;//记录步数 } } } } return 0; }
dfs篇：
额。。。dfs。。未完待续。。。
唉唉唉点个赞再走啊。。
