1 //卡了很长时间，后来发现别人的题解vis是三维。
 2 //显然要用到优先队列，本题的vis不是只访问一次，可以访问P次，因为以不同的能量值经过同一点的方案肯定是不同的。
 3 #include<iostream>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<queue>
 7 using namespace std;
 8 int n,m,t,p;
 9 char map[82][82];
10 bool vis[82][82][82];
11 int dir[4][2]={1,0,-1,0,0,1,0,-1};
12 struct Lu
13 {
14     int x,y,cnt,mag;
15     friend bool operator<(Lu a,Lu b)
16     {
17         return a.cnt>b.cnt;
18     }
19 };
20 int bfs(int sx,int sy)
21 {
22     priority_queue<Lu>q;
23     Lu L1,L2;
24     L1.x=sx;L1.y=sy;L1.cnt=0;L1.mag=p;
25     vis[sx][sy][p]=1;
26     q.push(L1);
27     while(!q.empty())
28     {
29         L2=q.top();
30         q.pop();
31         if(L2.cnt>t)
32         return 10000000;
33         if(map[L2.x][L2.y]==‘L‘)
34         return L2.cnt;
35         for(int i=0;i<4;i++)
36         {
37             L1.x=L2.x+dir[i][0];
38             L1.y=L2.y+dir[i][1];
39             if(L1.x<0||L1.x>=n||L1.y<0||L1.y>=m) continue;
40             if(map[L1.x][L1.y]==‘#‘) continue;
41             if(L2.mag>0&&!vis[L1.x][L1.y][L2.mag-1])
42             {
43                 L1.cnt=L2.cnt+1;
44                 L1.mag=L2.mag-1;
45                 vis[L1.x][L1.y][L1.mag]=1;
46                 q.push(L1);
47             }
48             if(map[L1.x][L1.y]!=‘@‘&&map[L2.x][L2.y]!=‘@‘&&!vis[L1.x][L1.y][L2.mag])
49             {
50                 L1.cnt=L2.cnt+2;
51                 L1.mag=L2.mag;
52                 vis[L1.x][L1.y][L2.mag]=1;
53                 q.push(L1);
54             }
55         }
56     }
57     return 10000000;
58 }
59 int main()
60 {
61     int sx,sy,k=0;
62     while(scanf("%d%d%d%d",&n,&m,&t,&p)!=EOF)
63     {
64         k++;
65         for(int i=0;i<n;i++)
66         {
67             scanf("%s",map[i]);
68             for(int j=0;j<m;j++)
69             if(map[i][j]==‘Y‘)
70             {
71                 sx=i;sy=j;
72             }
73         }
74         memset(vis,0,sizeof(vis));
75         int ans=bfs(sx,sy);
76         printf("Case %d:\n",k);
77         if(ans>t) printf("Poor Yifenfei, he has to wait another ten thousand years.\n");
78         else printf("Yes, Yifenfei will kill Lemon at %d sec.\n",ans);
79     }
80     return 0;
81 }