首页 > 代码库 > POJ 2251 Dungeon Master

POJ 2251 Dungeon Master

2024-09-07 09:27:42   218人阅读

题目戳这

题意：给你个三维的字符，从S走到E，点代表空的空间，#代表这个坐标不能走，每走一格就一格时间点，问最短需要多长时间从S走到E。

思路：直接建一个三维的数组，然后bfs，不用搜到一条路再搜一条路，直接bfs，最先搜到的时间点就是最短的时间点。

P.S.一开始还想着怎么一边输入一边搜，后面才想到直接建三维数组，然后又是那样，想到dfs，把搜到的时间一个一个对比，然后才想到，bfs最先搜到的就是最短的时间点。然后交上去，拼命爆内存，我就想着为啥这么小的三维数组都爆内存，然后才知道，我标记的地方不对，应该一把这个坐标放到队列里面的时候就标记起来，而不是队列轮到那个坐标的时候才标记，就是这一点，拼命爆内存，我擦。

技术分享 
 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<string.h>
 4 #include<math.h>
 5 #include<algorithm>
 6 #include<vector>
 7 #include<string>
 8 #include<queue>
 9 #include<map>
10 #include<stack>
11 #include<set>
12 #define ll long long
13 #define maxn 100010
14 #define PI acos(-1.0)    //圆周率
15 const ll INF = 1e18;
16 using namespace std;
17 struct node
18 {
19     int x,y,z;
20     int step;
21 }fi;
22 queue <node> q;
23 int l,r,c;
24 string maze[35][35];
25 int vis[35][35][35];
26 int ff[6][3]={1,0,0,
27               -1,0,0,
28               0,1,0,
29               0,-1,0,
30               0,0,1,
31               0,0,-1};
32 bool judge(int q,int w,int e)
33 {
34     if(q<l&&q>=0&&w<r&&w>=0&&e<c&&e>=0)  return true;
35     else  return false;
36 }
37 int bfs()
38 {
39     q.push(fi);
40     vis[fi.x][fi.y][fi.z]=1;
41     while(!q.empty())
42     {
43         node temp=q.front();
44         q.pop();
45 
46         if(maze[temp.x][temp.y][temp.z]==‘E‘)  return temp.step;
47 
48         for(int i=0;i<6;i++)
49         {
50             fi.x=temp.x+ff[i][0];
51             fi.y=temp.y+ff[i][1];
52             fi.z=temp.z+ff[i][2];
53             fi.step=temp.step+1;
54 
55             if(judge(fi.x,fi.y,fi.z)&&maze[fi.x][fi.y][fi.z]!=‘#‘&&!vis[fi.x][fi.y][fi.z])
56             {
57                 q.push(fi);
58                 vis[fi.x][fi.y][fi.z]=1;
59             }
60         }
61     }
62 
63     return -1;
64 }
65 int main()
66 {
67     while(scanf("%d %d %d",&l,&r,&c)!=EOF&&l&&r&&c)
68     {
69         memset(vis,0,sizeof(vis));
70 
71         while(!q.empty())  q.pop();
72 
73         for(int i=0;i<l;i++)
74         {
75             for(int j=0;j<r;j++)
76             {
77                 cin>>maze[i][j];
78                 for(int k=0;k<c;k++)
79                 {
80                     if(maze[i][j][k]==‘S‘)
81                     {
82                         fi.x=i;
83                         fi.y=j;
84                         fi.z=k;
85                         fi.step=0;
86                     }
87                 }
88             }
89         }
90 
91         int ans=bfs();
92         if(ans==-1)  printf("Trapped!\n");
93         else  printf("Escaped in %d minute(s).\n",ans);
94     }
95 
96     return 0;
97 }
View Code


 


 
POJ 2251 Dungeon Master






























        

            
                
                  
                
                

                    联系

                    我们