|
Problem Description
It was ten thousand years, after Demon Lemon caught Yifenfei’s love. In order to revenge and save his love, Yifenfei have been practising sword all day long and his Kongfu skills becomes so powerful that he can kill Demon Lemon immediately. Recently, Yifenfei have found Lemon’s castle, and now he is going to kill Lemon. At the same time, hearing about the terrible news, Demon Lemon is now preparing for escaping...
Now Yifenfei has got the map of the castle. Here are all symbols of the map: Only one ‘Y’ Indicates the start position of Yifenfei. Only one ‘L’ Indicates the position of Demon Lemon. ‘.’ Indicate the road that Yifenfei can walk on it, or fly over it. ‘#’ Indicate the wall that Yifenfei can not walk or flay through it. ‘@’ Indicate the trap that Yifenfei can not walk on it, but can fly over it. Yifenfei can walk or fly to one of up, down, left or right four directions each step, walk costs him 2 seconds per step, fly costs him 1 second per step and 1 magic power. His magic power will not increased, and if his magic power is zero, he can not fly any more. Now Yifenfei asks you for helping him kill Demon Lemon smoothly. At the same time, Demon Lemon will Leave the castle Atfer T seconds. If Yifenfei can’t kill Demon Lemon this time, he have to wait another ten thousand years. |
|
Input
Lots of test cases, please process to end of file. In each test
case, firstly will have four integers N, M, T, P(1 <= N, M, P <=
80, 1 <= T <= 100000), indicates the size of map N * M, the
Lemon’s leaving time(after T seconds, Lemon will disappeared) and
Yifenfei’s magic power. Then an N * M two-dimensional array follows
indicates the map.
|
|
Output
For each test case, first Print a line “Case C:”, C indicates the
case number. Then, if Yifenfei can kill Demon Lemon successfully, Print
“Yes, Yifenfei will kill Lemon at T sec.”, T indicates the minimum
seconds he must cost. Otherwise, Print ”Poor Yifenfei, he has to wait
another ten thousand years.”
|
|
Sample Input
2 3 2 2 Y@L ### 2 3 4 1 Y@L ### 2 3 4 0 Y.L ### 2 3 3 0 Y.L ### |
|
Sample Output
Case 1: Yes, Yifenfei will kill Lemon at 2 sec. Case 2: Poor Yifenfei, he has to wait another ten thousand years. Case 3: Yes, Yifenfei will kill Lemon at 4 sec. Case 4: Poor Yifenfei, he has to wait another ten thousand years. Hint
Hint Case 1: Yifenfei cost 1 second and 1 magic-power fly to ‘@’, but he can not step on it, he must cost another 1 second and 1 magic-power fly to ‘L’ and kill Lemon immediately. Case 2: When Yifenfei Fly to ‘@’, he has no power to fly, and is killed by trap. |
思路：BFS，看了别人的AC代码，终于开始用优先队列了！那么优先队列是个什么东东呢?先自己百度，就说可以把队列中的元素按一定顺序排列，好好啊！
有一些细节错误害得我检查了好久！
1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 4 using namespace std; 5 6 struct qq 7 { 8 int x,y,step,p; 9 bool friend operator < (const qq &a,const qq &b) 10 { 11 if (a.step==b.step) 12 return a.p<b.p; 13 return a.step>b.step; 14 } 15 } s,ya; 16 17 priority_queue<qq> q; 18 19 const int dx[]={1,-1,0,0}; 20 const int dy[]={0,0,1,-1}; 21 bool f[82][82][82]; 22 char map[82][82]; 23 int power,t,n,m,ax,ay,i,cnt=0,tot=0; 24 25 bool pd() 26 { 27 if (map[ya.x][ya.y]=='#') return true; //也就是不能到达，直接退出 28 if (ya.x>=0 && ya.x<n && ya.y>=0 && ya.y<m && not f[ya.x][ya.y][ya.p]) 29 return false; 30 return true; 31 } 32 33 void judge() 34 { 35 if (s.p>0) //也就是说这一步是可以用能量的 36 for (i=0;i<4;i++) 37 { 38 ya.x=s.x+dx[i]; 39 ya.y=s.y+dy[i]; 40 ya.p=s.p-1; //能量减少1 41 ya.step=s.step; 42 if (not pd()) 43 { 44 f[ya.x][ya.y][ya.p]=true; 45 ya.step++; //步数增加1 46 q.push(ya); 47 } 48 } 49 if (map[s.x][s.y]=='@') return; //在@的时候，如果不能移动，则挂了 50 for (i=0;i<4;i++) 51 { 52 ya.x=s.x+dx[i]; 53 ya.y=s.y+dy[i]; 54 ya.p=s.p; 55 ya.step=s.step; //这一句一定要加上，否则就未清零啊！ 56 if (not pd() && ( map[ya.x][ya.y]=='.' || map[ya.x][ya.y]=='L' )) 57 { 58 f[ya.x][ya.y][ya.p]=true; //这句话把我整惨了！ 59 ya.step+=2; 60 q.push(ya); 61 } 62 } 63 } 64 65 void bfs() 66 { 67 memset(f,false,sizeof(f)); 68 while (!q.empty()) 69 q.pop(); 70 s.x=ax; s.y=ay; s.p=power; s.step=0; 71 f[s.x][s.y][s.step]=true; 72 q.push(s); 73 while (!q.empty()) 74 { 75 s=q.top(); 76 q.pop(); 77 if (map[s.x][s.y]=='#') break; 78 if (map[s.x][s.y]=='L') 79 { 80 if (t>=s.step) 81 printf("Yes, Yifenfei will kill Lemon at %d sec.\n",s.step); 82 else printf("Poor Yifenfei, he has to wait another ten thousand years.\n"); 83 return; 84 } 85 judge(); 86 } 87 printf("Poor Yifenfei, he has to wait another ten thousand years.\n"); 88 } 89 90 91 void init() 92 { 93 while (scanf("%d%d%d%d",&n,&m,&t,&power)!=EOF) 94 { 95 cnt++; 96 printf("Case %d:\n",cnt); 97 for(int i=0;i<n;i++) 98 { 99 scanf("%s",map[i]); 100 for(int j=0;j<m;j++) 101 if(map[i][j]=='Y') 102 { 103 ax=i; 104 ay=j; 105 } 106 } 107 // printf("ax:%d ay:%d\n",ax,ay); 108 bfs(); 109 } 110 } 111 112 int main () 113 { 114 init(); 115 return 0; 116 }