HDU 2653 Waiting ten thousand years for Love

题目链接~~>

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

解题思路：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 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/23278563