Source : - Sealed - Time limit : 2 sec Memory limit : 32 M Submitted : 77, Accepted : 31 Goddess is a super Xueba. He even keeps studying when she is sleeping.Days ago she made a very complicated dream, where she was told that the answers to the final exams hides somewhere in her dream and she had to find it out. Let's assume that Goddess's dream is a two-dimensional labyrinth consisted of r rows and c columns. But because of Goddess's high IQ, she sometimes makes dreams in her dreams, which means there can be k levels of dreams and the answer always hides in her deepest dream. That drives Goddess crazy. Can you help her get the answers to the final exams as soon as possible? Input There are multiple testcases. Each starts with three integers k,r,c, 1<=k,r,c<=30 Then there will follow k blocks consisted of r lines each containing c characters. Each character describes one cell of Goddess's dream. '.'means the cell is empty and you can step on it. '#'means there are rocks and you cannot be there. 'S'means the initial position of you in the first level of dreams. 'E'means the destination you need to reach in the deepest dream. Every step takes exactly 1 minute. Moving to an adjacent dream(including the upper or lower dream) also takes 1 minute. You need to find the fastest way to get the answer. 0 0 0 means the end of test cases. Output Got the answer in x minutes! where x is replaced by the time you take to find the answer. If you can't find a way to the destination, just print "Goddess will fail her final exams." Sample Input 3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0 Sample Output Got the answer in 11 minutes! Goddess will fail her final exams. [cpp] /* 題目：H題 http://acm.hit.edu.cn/hoj/problem/view?id=4000600 題目大意：給出k塊r*c的矩陣，即一個三維矩陣 第一層矩陣中有一個start 最有一層有一個end，從start出發，走一格或跳到下一層矩陣對應位置需要1分鐘，求到end最快多少分鐘； #為不可走 .為可走 開始位置為S 結束位置為E 解題思路：BFS，從start開始(為0分鐘)對當前位置的前後左右下5個方向判斷是否滿足條件(即是否為'.'),求時間直到end。 比以前做的那些2維的矩陣多考慮了一個方向而已 */ #include<stdio.h> #include<queue> using namespace std; char map[50][50][50]; int n,m,k,s_x,s_y,e_x,e_y; struct haha { int z; int x; int y; int val; friend bool operator<(struct haha a,struct haha b) { return a.val>b.val; } }q,temp; int step[5][3]={0,1,0, 0,-1,0, 0,0,1, 0,0,-1, 1,0,0}; void BFS() { int i,xx,yy,zz,ans=999999999; priority_queue<haha>que; q.z=1; q.x=s_x; q.y=s_y; q.val=0; que.push(q); while(!que.empty()) { temp=que.top(); que.pop(); if(temp.z==k&&temp.x==e_x&&temp.y==e_y) { ans=temp.val; printf("Got the answer in %d minutes!\n",ans); break; } for(i=0;i<5;i++) { zz=temp.z+step[i][0]; xx=temp.x+step[i][1]; yy=temp.y+step[i][2]; if(zz>=1&&zz<=k&&xx>=1&&xx<=n&&yy>=1&&yy<=m&&map[zz][xx][yy]!='#') { q.x=xx; q.y=yy; q.z=zz; q.val=temp.val+1; map[zz][xx][yy]='#'; que.push(q); } } } if(ans==999999999) printf("Goddess will fail her final exams.\n"); } int main() { int i,j,t; while(scanf("%d %d %d",&k,&n,&m)!=EOF) { if(k==0&&n==0&&m==0) break; for(t=1;t<=k;t++) { for(i=1;i<=n;i++) { scanf("%s",map[t][i]+1); for(j=1;j<=m;j++) { if(map[t][i][j]=='S') {s_x=i;s_y=j;} if(map[t][i][j]=='E') {e_x=i;e_y=j;} } } } BFS(); } return 0; }
