首先，对于一个 '@' 飞上去，飞下来都要耗1点魔力，所以是两点= =
然后站在同一格 魔力可能不同，所以要增加一维。
还有当前搜到的不一定是最小。
别的也没啥。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6 const int N=100; 7 int d[4][2]={1,0,-1,0,0,1,0,-1}; 8 struct node{ 9 int x,y,t,mag; 10 }s,nxt; 11 char map[N][N]; 12 int vis[N][N][N]; 13 queue <node> q; 14 int n,m,t,mag,ans; 15 bool check(node& a) 16 { 17 return 0<=a.x&&a.x<n&&0<=a.y&&a.y<m&&map[a.x][a.y]!='#' ; 18 } 19 void bfs() 20 { 21 while(!q.empty()) q.pop(); 22 memset(vis,0,sizeof(vis)); 23 q.push(s); 24 while(!q.empty()) 25 { 26 s=q.front(); 27 q.pop(); 28 if(map[s.x][s.y]=='L') 29 { 30 ans=min(s.t,ans); 31 continue; 32 } 33 for(int i=0;i<4;++i) 34 { 35 nxt.x=s.x+d[i][0]; 36 nxt.y=s.y+d[i][1]; 37 if(!check(nxt)) continue; 38 if(s.mag && !vis[nxt.x][nxt.y][s.mag-1]) 39 { 40 vis[nxt.x][nxt.y][s.mag-1]=1; 41 nxt.t=s.t+1; 42 nxt.mag=s.mag-1; 43 q.push(nxt); 44 } 45 if(map[s.x][s.y]!='@' && map[nxt.x][nxt.y]!='@' && !vis[nxt.x][nxt.y][s.mag]) 46 { 47 vis[nxt.x][nxt.y][s.mag]=1; 48 nxt.t=s.t+2; 49 nxt.mag=s.mag; 50 q.push(nxt); 51 } 52 } 53 } 54 } 55 int main() 56 { 57 int k=0; 58 while(~scanf("%d%d%d%d",&n,&m,&t,&mag)) 59 { 60 for(int i=0;i<n;i++) 61 { 62 scanf("%s",map[i]); 63 for(int j=0;j<m;j++) 64 { 65 if(map[i][j]=='Y') 66 s.x=i,s.y=j; 67 } 68 } 69 s.t=0,s.mag=mag; 70 ans=100005; 71 bfs(); 72 printf("Case %d: ",++k); 73 if(ans<=t) printf("Yes, Yifenfei will kill Lemon at %d sec. ",ans); 74 else puts("Poor Yifenfei, he has to wait another ten thousand years."); 75 } 76 }