首页 > 代码库 > POJ 3984 路径输出

POJ 3984 路径输出

2024-10-26 21:38:02   207人阅读

迷宫问题

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)

Source

思路：bfs+输出路径

代码：

 1 #include "cstdio"
 2 #include "stdlib.h"
 3 #include "iostream"
 4 #include "algorithm"
 5 #include "string"
 6 #include "cstring"
 7 #include "queue"
 8 #include "cmath"
 9 #include "vector"
10 #include "map"
11 #include "set"
12 #define mj
13 #define db double
14 #define ll long long
15 using namespace std;
16 const int N=1e8+2;
17 const int mod=1e9+7;
18 const ll inf=1e16+10;
19 typedef pair<int,int> P;
20 vector<P> m;
21 queue<P> q;
22 P fa[12][12];
23 
24 int  s[12][12];
25 int d[12][12];
26 int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
27 void pt(P u){
28     while(1){
29         m.push_back(u);//从后往前找父节点
30         if(u==P(0,0)) break;//根节点
31         u=fa[u.first][u.second];
32     }
33     for(int i=(int)m.size()-1;i>=0;i--)//从根节点开始依次输出路径
34         printf("(%d, %d)\n",m[i].first,m[i].second);
35 }
36 void bfs()
37 {
38     for(int i=0;i<5;i++){
39         for(int j=0;j<5;j++){
40             d[i][j]=N;
41         }
42     }
43     q.push(P(0,0));
44     d[0][0]=0;
45     while(q.size()){
46         P p;
47         p=q.front(),q.pop();
48         if(p.first==4&&p.second==4) {
49             pt(p);
50             return;
51         }
52         for(int i=0;i<4;i++){
53             int nx=p.first+dx[i],ny=p.second+dy[i];
54             if(0<=nx&&nx<5&&0<=ny&&ny<5&&!s[nx][ny]&&d[nx][ny]==N){
55                 d[nx][ny]=d[p.first][p.second]+1;
56                 fa[nx][ny]=p;/保存
57                 q.push(P(nx,ny));
58             }
59         }
60 
61 
62     }
63 }
64 int main()
65 {
66     memset(s,-1, sizeof(s));
67     for(int i=0;i<5;i++){
68         for(int j=0;j<5;j++){
69             scanf("%d",&s[i][j]);
70         }
71     }
72     bfs();
73     return 0;
74 }

 

POJ 3984 路径输出


联系
我们