学步园

题目链接~~>

做题感悟：这题有点失败，没考虑到必须用三维标记，开始感觉用二维就可以的，但是后来看到别人用三维才考虑到这样有的点就遍历不到。

解题思路：BFS + 优先队列 ：如果一个格子不是 @ 或者到达的格子也不为 @  那么就可以走过去 | | 飞过去，剩下的情况必须飞过去。（如果两个@相连且你从其中一个到达另一个只需要一个magic power 就可以）。

代码：

#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define LEN   sizeof(struct node)
#define pret(a,b) memset(a,b,sizeof(a))
#define lld __int64
const double PI = 3.1415926 ;
const double INF = 999999999 ;
const double esp = 1e-4 ;
const lld  md= 2810778 ;
const int MX = 85 ;
int n,m,tx,kx ;
char s[MX][MX] ;
bool vis[MX][MX][MX] ;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1} ;
struct node
{
    int x,y,step,p ;
    friend bool operator < (const node &a,const node &b) // 优先队列
    {
            return a.step > b.step ;
    }
} ;
bool search(int x,int y)
{
    if(x<0||y<0||x>=n||y>=m||s[x][y]=='#')
        return false;
        return true ;
}
int bfs(int x,int y,int kx)
{
    int sx,sy ;
    priority_queue<node>q ;
    node curt,next ;
    memset(vis,false,sizeof(vis)) ;
    curt.x=x ;
    curt.y=y ;
    curt.step=0 ;
    curt.p=kx ;
    vis[x][y][kx]=true ;
    q.push(curt) ;
    while(!q.empty())
    {
        curt=q.top() ;
        q.pop() ;
        if(curt.step>tx) return -1 ; // 剪枝最少的时间都大于 tx so……
        if(s[curt.x][curt.y]=='L')
              return  curt.step ;
        for(int i=0 ;i<4 ;i++)
        {
            next.x=sx=curt.x+dx[i] ;
            next.y=sy=curt.y+dy[i] ;
            next.p=curt.p ;
            if(search(sx,sy))
            {
                if(s[curt.x][curt.y]!='@'&&s[sx][sy]!='@'&&!vis[sx][sy][next.p]&&curt.step+2<=tx)// 走过去
                {
                    next.step=curt.step+2 ;
                    vis[sx][sy][next.p]=true ;
                    q.push(next) ;
                }
                if(next.p>0&&!vis[sx][sy][next.p-1]&&curt.step+1<=tx) // 飞过去
                {
                    next.p-- ;
                    next.step=curt.step+1 ;
                    vis[sx][sy][next.p]=true ;
                    q.push(next) ;
                }
            }
        }
    }
    return -1 ;
}
int main()
{
    int sx,sy,q=1 ;
    while(~scanf("%d%d%d%d",&n,&m,&tx,&kx))
    {
        for(int i=0 ;i<n ;i++)
        {
            scanf("%s",s[i]) ;
            for(int j=0 ;j<m ;j++)
              if(s[i][j]=='Y')
              {
                  sx=i ;
                  sy=j ;
              }
        }
        int mx=bfs(sx,sy,kx) ;
        printf("Case %d:\n",q++) ;
        if(mx!=-1)
                printf("Yes, Yifenfei will kill Lemon at %d sec.\n",mx) ;
        else
                printf("Poor Yifenfei, he has to wait another ten thousand years.\n") ;
    }
    return 0 ;
}