HDU 2579 Dating with girls(2)

题目链接~~>

做题感悟：这题注意它好久了，只是一直没有好的想法，正好感觉无聊于是下定决心A掉它，于是AC，有时做题真的取决于你想不想去做的问题。本以为自己的想法很好，但是看到网上别人的代码，顿时感觉被打击了。唯一值得高兴的是我的时间比他的短。

解题思路：我的思路就不说了，有点麻烦。因为在 k 时间石头会消失，但是当你到达那一点是不一定刚好（有可能再走一下回头路再次到这一点时石头就会消失），可以通过三维数组标记，第三维是时间模 k 的余数，这样就可以标记整个图。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      int n,m,k ;
     
    
   

    

     

    
    

     

      bool vis[105][105][15] ;
     
    
   

    

     

    
    

     

      char s[105][105] ;
     
    
   

    

     

    
    

     

      int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1} ;
     
    
   

    

     

    
    

     

      struct zhang
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,y,step ;
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      bool search(int x,int y,int step) //判断是否可以走
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(x<0||y<0||x>=n||y>=m||vis[x][y][step%k])
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     
 if(s[x][y]=='#'&&step%k!=0)
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     
 return true ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int bfs(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 queue<zhang>q ;
     
    
   

    

     

    
    

     
 memset(vis,false,sizeof(vis)) ;
     
    
   

    

     

    
    

     

       zhang curt,next ;
     
    
   

    

     

    
    

     

       curt.x=x ;
     
    
   

    

     

    
    

     

       curt.y=y ;
     
    
   

    

     

    
    

     

       vis[x][y][0]=true ;
     
    
   

    

     

    
    

     

       curt.step=0 ;
     
    
   

    

     

    
    

     

       q.push(curt) ;
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       curt=q.front() ;
     
    
   

    

     

    
    

     

       q.pop() ;
     
    
   

    

     

    
    

     
 if(s[curt.x][curt.y]=='G')
     
    
   

    

     

    
    

     
 return  curt.step ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<4 ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       next.x=curt.x+dx[i] ;
     
    
   

    

     

    
    

     

       next.y=curt.y+dy[i] ;
     
    
   

    

     

    
    

     

       next.step=curt.step+1 ;
     
    
   

    

     

    
    

     
 if(search(next.x,next.y,next.step))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       vis[next.x][next.y][next.step%k]=true ;
     
    
   

    

     

    
    

     

       q.push(next) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return -1 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T,sx,sy ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d%d",&n,&m,&k) ;
     
    
   

    

     

    
    

     
 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) ;
     
    
   

    

     

    
    

     
 if(mx!=-1)
     
    
   

    

     

    
    

     
 printf("%d\n",mx) ;
     
    
   

    

     

    
    

     
 else printf("Please give me another chance!\n") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

本人代码~>

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

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