POJ 3984

迷宫问题

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 23870		Accepted: 13902

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

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

真的是太菜了 不知道怎么保存路径 蠢到用单链表链接 然后用栈逆序输出 真的菜哭了，必须要努力学习新姿势，怎么可以这么菜！！！！~

还是纪念一下吧

AC代码

 1 #include <stdio.h>                  //可以看做图来解答，两个节点都为0即可看做一条边，仅限上下左右相邻的节点之间
 2 #include <math.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 #include <iostream>
 6 #include <sstream>
 7 #include <stack>
 8 #include <queue>
 9 #include <vector>
10 #include <algorithm>
11 #define maxn 100010
12 using namespace std;
13 typedef long long ll;
14 int visit[10][10]={0};
15 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//四个方向
16 typedef struct node
17 {
18   int x;
19   int y;                        //节点坐标
20   int val;                      //该点的值0或1
21   struct node *fr;              //记录上个节点
22 }node,*nlist;
23 node f[10][10];
24 void read()
25 {
26   for(int i=0;i<5;i++)
27   {
28     for(int j=0;j<5;j++)
29      {
30         cin>>f[i][j].val;
31         f[i][j].x=i;
32         f[i][j].y=j;
33       }
34   }
35 }
36 bool judege(int n,int m)           //满足三个条件才可以入队列，没遍历过，该节点值不为1（为1走不通），注意边界
37 {
38   if(f[n][m].val==1)
39     return false;
40   if(visit[n][m]==1)
41     return false;
42   if(n<0||n>4||m<0||m>4)
43     return false;
44   return true;
45 }
46 void BFS(int sx,int sy,int ex,int ey)  //起点、终点
47 {
48   queue<nlist> q;
49   visit[sx][sy]=1;
50   nlist b=&f[sx][sy];
51   b->fr=NULL;
52   q.push(b);
53   while(!q.empty())
54   {
55     nlist cur;
56     cur=q.front();
57     q.pop();
58     for(int i=0;i<4;i++)               //遍历周围节点
59     {
60       int x=dir[i][0]+cur->x;
61       int y=dir[i][1]+cur->y;
62       if(judege(x,y)==true)
63       {                               //判断是否可以入队
64         nlist n=&f[x][y];
65         n->fr=cur;                     //记录路径QAQ...
66         q.push(n);
67         visit[x][y]=1;
68         if(x==ex&&y==ey)              //搜到终点直接结束
69           return;
70       }
71     }
72   }
73 }
74 void print(int sx,int sy,int ex,int ey)
75 {
76   stack<nlist> s;
77   nlist p=&f[ex][ey];
78   s.push(p);
79   while(p->fr!=NULL)
80   {
81     p=p->fr;
82     s.push(p);
83   }
84   while(!s.empty())
85   {
86     nlist n=s.top();
87     cout<<"("<<n->x<<", "<<n->y<<")"<<endl;
88     s.pop();
89   }
90 }
91 int main(int argc, char const *argv[])
92 {
93   read();
94   BFS(0,0,4,4);
95   print(0,0,4,4);
96   return 0;
97 }

加油加油~~