洛谷 P2360 地下城主

题目传送门

解题思路:

一道三维的迷宫,bfs即可(因为要求最短步数).

读入的时候总是出错,经过twh的耐心教导后,知道如果直接用字符数组读,每行会多读一个回车,直接读字符串就可以避免这个问题.

AC代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<queue>
 4 #include<cstring>
 5 
 6 using namespace std;
 7 
 8 int l,r,c,x,y,h,ans[31][31][31],ansx,ansy,ansh;
 9 char a[31][31][31];
10 int way[6][3] = {{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1}};
11 bool p[31][31][31];
12 string ll;
13 
14 inline void _scanf() {
15     scanf("%d%d%d",&l,&r,&c);
16     for(int i = 1;i <= l; i++) {
17         for(int j = 1;j <= r; j++){
18             cin >> ll;
19             for(int o = 1;o <= ll.length(); o++) {
20                 a[i][j][o] = ll[o-1];
21                 if(a[i][j][o] == 'S') {
22                     x = j;
23                     y = o;
24                     h = i;
25                 }
26                 if(a[i][j][o] == 'E') {
27                     ansx = j;
28                     ansy = o;
29                     ansh = i;
30                 }
31             }
32         }
33     }            
34 }
35 
36 inline void bfs() {
37     memset(ans,-1,sizeof(ans));
38     queue<int> x1,y1,h1;
39     x1.push(x);
40     y1.push(y);
41     h1.push(h);
42     p[h][x][y] = 1;
43     ans[h][x][y] = 0;
44     while(!x1.empty()) {
45         x = x1.front();
46         x1.pop();
47         y = y1.front();
48         y1.pop();
49         h = h1.front();
50         h1.pop();
51         for(int i = 0;i < 6; i++) {
52             int nx = x + way[i][0];
53             int ny = y + way[i][1];
54             int nh = h + way[i][2];
55             if(nx < 1 || nx > r || ny < 1 || ny > c || nh < 1 || nh > l) continue;
56             if(a[nh][nx][ny] == '#') continue;
57             if(!p[nh][nx][ny]) {
58                 p[nh][nx][ny] = 1;
59                 ans[nh][nx][ny] = ans[h][x][y] + 1;
60                 x1.push(nx);
61                 y1.push(ny);
62                 h1.push(nh);
63             }
64         }
65     }
66 }
67 
68 inline void _printf() {
69     if(ans[ansh][ansx][ansy] == -1)
70         printf("Trapped!");
71     else
72         printf("Escaped in %d minute(s).",ans[ansh][ansx][ansy]);
73 }
74 
75 int main()
76 {
77     _scanf();
78     bfs();
79     _printf();
80     return 0;
81 }