Waiting ten thousand years for Love
Time Limit: 10000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 615 Accepted Submission(s): 205
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.
Y@L
###
2 3 4 1
Y@L
###
2 3 4 0
Y.L
###
2 3 3 0
Y.L
###
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
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.
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std; const int MAX=80+10;
char Map[MAX][MAX];
int mark[MAX][MAX][MAX];//在位置i,j剩余魔力k是否标记
int n,m,t,p;
int dir[4][2]={0,1,0,-1,1,0,-1,0}; struct Node{
int x,y,time,m;
Node(){}
Node(int X,int Y,int Time,int M):x(X),y(Y),time(Time),m(M){}
bool operator<(const Node &a)const{
return time>a.time;
}
}start; priority_queue<Node>q;
int BFS(int &flag){
while(!q.empty())q.pop();
Node next,oq;
q.push(start);
mark[start.x][start.y][start.m]=flag;
while(!q.empty()){
oq=q.top();
q.pop();
if(Map[oq.x][oq.y] == 'L')return oq.time;
if(oq.time>t)return INF;
for(int i=0;i<4;++i){
next=Node(oq.x+dir[i][0],oq.y+dir[i][1],oq.time+1,oq.m);
if(next.x<0 || next.y<0 || next.x>=n || next.y>=m)continue;
if(Map[next.x][next.y] == '#')continue;
if(Map[next.x][next.y] != '@' && Map[oq.x][oq.y] != '@' && mark[next.x][next.y][next.m] != flag){
++next.time;
q.push(next);
mark[next.x][next.y][next.m]=flag;
}
if(next.m>0 && mark[next.x][next.y][next.m-1] != flag){
--next.m;
next.time=oq.time+1;
q.push(next);
mark[next.x][next.y][next.m]=flag;
}
}
}
return INF;
} int main(){
int num=0;
while(cin>>n>>m>>t>>p){
for(int i=0;i<n;++i)cin>>Map[i];
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(Map[i][j] == 'Y')start.x=i,start.y=j;
}
}
start.time=0,start.m=p;
int temp=BFS(++num);
cout<<"Case "<<num<<":\n";
if(temp>t)cout<<"Poor Yifenfei, he has to wait another ten thousand years."<<endl;
else cout<<"Yes, Yifenfei will kill Lemon at "<<temp<<" sec."<<endl;
}
return 0;
}