Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://poj.org/problem?id=2251
简单bfs，只不过是三维的。。。
唯一的坑点在输出上…
Escaped in %d minute(s)
这意思是答案为1输出minute,不为1输出minutes还是说是不是1都输出minute(s)? 试了下，答案是后者。
另：终于找到了好的读地图的方法。。。而不用担心回车符。
就是先读成字符串。
具体见代码
1
2
3 /*************************************************************************
4 > File Name: code/2015summer/searching/B.cpp
5 > Author: 111qqz
6 > Email: rkz2013@126.com
7 > Created Time: 2015年07月17日 星期五 16时47分46秒
8 ************************************************************************/
9
10 #include<iostream>
11 #include<iomanip>
12 #include<cstdio>
13 #include<algorithm>
14 #include<cmath>
15 #include<cstring>
16 #include<string>
17 #include<map>
18 #include<set>
19 #include<queue>
20 #include<vector>
21 #include<stack>
22 using namespace std;
23 #define REP(i, n) for (int i=0;i<int(n);++i)
24 typedef long long LL;
25 typedef unsigned long long ULL;
26 const int N=40;
27 char st[N][N][N];
28 int d[N][N][N];
29 int l,r,c;
30 int sx,sy,sz,tx,ty,tz;
31 int dirx[6]={1,-1,0,0,0,0};
32 int diry[6]={0,0,-1,1,0,0};
33 int dirz[6]={0,0,0,0,1,-1};
34
35 bool ok(int x,int y,int z)
36 {
37 if (z>=0&&z<l&&x>=0&&x<r&&y>=0&&y<c&&d[z][x][y]==-1&&st[z][x][y]!='#')
38 return true;
39 return false;
40 }
41
42 void bfs()
43 {
44 memset(d,-1,sizeof(d));
45 queue<int>x;
46 queue<int>y;
47 queue<int>z;
48 x.push(sx);
49 y.push(sy);
50 z.push(sz);
51 d[sz][sx][sy]=0;
52 while (!x.empty()&&!y.empty()&&!z.empty())
53 {
54 int prex = x.front();x.pop();
55 int prey = y.front();y.pop();
56 int prez = z.front();z.pop();
57 for ( int i = 0 ; i < 6 ; i++ )
58 {
59 int newx = prex+dirx[i];
60 int newy = prey+diry[i];
61 int newz = prez+dirz[i];
62 bool flag = ok(newx,newy,newz);
63 if (flag)
64 {
65 d[newz][newx][newy]=d[prez][prex][prey]+1;
66 x.push(newx);
67 y.push(newy);
68 z.push(newz);
69 }
70 }
71
72 }
73 }
74
75 int main()
76 {
77 while (scanf("%d %d %d",&l,&r,&c))
78 {
79 if (l==0&&r==0&&c==0)
80 break;
81 for ( int i = 0 ; i < l ; i++)
82 {
83 for ( int j = 0 ; j < r; j++)
84 scanf("%s",st[i][j]);
85 }
86 for ( int i = 0 ; i < l ; i++ )
87 {
88 for ( int j = 0 ; j < r ; j ++)
89 {
90 for ( int k = 0 ; k < c ; k++ )
91 {
92 if (st[i][j][k]=='S')
93 {
94 sx = j;
95 sy = k;
96 sz = i;
97 }
98 if (st[i][j][k]=='E')
99 {
100 tx = j;
101 ty = k;
102 tz = i;
103 }
104
105 }
106 }
107 }
108 bfs();
109 int ans = d[tz][tx][ty];
110 if (ans==-1)
111 {
112 printf("Trapped!\n");
113 }
114 else
115 {
116 // if (ans==1)
117 // printf("Escaped in 1 minute.\n");
118 // else printf("Escaped in %d minutes.\n",ans);
119 printf("Escaped in %d minute(s).\n",ans);
120 }
121
122 }
123 }