题意：从起点到终点，bfs
不同的是对于图中的点，可能走多次，分别是在不同的时刻。
myhash[ i ][ j ][ t%k ]=1:表示坐标（ i，j ）在 t%k 时刻走过，接下来再出现 t%k 就不用再走一次了。
对于‘.’能入队，必须满足在该时刻没走过这个特点
对于‘#’能入队，必须满足 该时刻没走过 且 该时刻 t%k==0 ；
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<stdlib.h> 5 #include<queue> 6 using namespace std; 7 const int maxn = 105; 8 const int inf=999999; 9 int n,m,k; 10 char mat[ maxn ][ maxn ]; 11 int myhash[ maxn ][ maxn ][ 12 ]; 12 const int dx[]={0,0,1,-1}; 13 const int dy[]={1,-1,0,0}; 14 struct node{ 15 int x,y,t; 16 }mys,mye,p,pp; 17 int ans; 18 19 void bfs( ){ 20 p.x=mys.x,p.y=mys.y,p.t=0; 21 queue<node>q; 22 q.push( p ); 23 memset( myhash,0,sizeof(myhash) ); 24 mat[ p.x ][ p.y ]=mat[ mye.x ][ mye.y ]='.'; 25 while( !q.empty() ){ 26 p=q.front(),q.pop(); 27 for( int kk=0;kk<4;kk++ ){ 28 pp.x=p.x+dx[ kk ],pp.y=p.y+dy[ kk ],pp.t=p.t+1; 29 if( pp.x<0||pp.x>=n||pp.y<0||pp.y>=m ) continue; 30 if( pp.x==mye.x && pp.y==mye.y ){ 31 ans=min( ans,pp.t ); 32 return ; 33 } 34 if(mat[ pp.x ][ pp.y ]=='.' && myhash[ pp.x ][ pp.y ][ pp.t%k ]==0 ){ 35 myhash[ pp.x ][ pp.y ][ pp.t%k ]=1; 36 q.push( pp ); 37 } 38 else if( mat[ pp.x ][ pp.y ]=='#' && pp.t%k==0 && myhash[ pp.x ][ pp.y ][ pp.t%k ]==0 ){ 39 myhash[ pp.x ][ pp.y ][ pp.t%k ]=1; 40 q.push( pp ); 41 } 42 } 43 } 44 return ; 45 } 46 47 int main(){ 48 int T; 49 scanf("%d",&T); 50 while( T-- ){ 51 scanf("%d%d%d",&n,&m,&k); 52 for( int i=0;i<n;i++ ){ 53 scanf("%s",mat[ i ]); 54 for( int j=0;j<m;j++ ){ 55 if( mat[ i ][ j ]=='Y' ) mys.x=i,mys.y=j; 56 else if( mat[ i ][ j ]=='G' )mye.x=i,mye.y=j; 57 } 58 } 59 ans=inf; 60 bfs(); 61 if( ans==inf ) printf("Please give me another chance!\n"); 62 else printf("%d\n",ans); 63 } 64 return 0; 65 }