HDU 2102 A计划

该题是一道典型的搜索题，

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Node
{int x, y;int time;int flag;
}q[100024];
int d[4][2]={ 0,1,1,0,0,-1,-1,0  };
int N,M;
char map[2][13][13];
void getxy( int &X,int &Y,int &K )
{for( int k=0;k<2;k++ )for( int i=1;i<=N;i++ )for( int j=1;j<=M;j++ ){if( map[k][i][j]=='S' ){K=k;X=i;Y=j;return ;    }     }     
}
int push( int x,int y,int time,int flag,int end )
{Node t;t.x=x; t.y=y;t.time=time;t.flag=flag;q[end++]=t;return end;    
}
bool judge( int x,int y,int flag,int time )
{if( map[flag][x][y]!=0 && map[flag][x][y]!='*'&&time>=0 )return true;else return false;    
}
bool BFS( int x,int y,int k,int time )
{  int hash[2][14][14]={0},first=0,end=0;end=push( x,y,time,k,end );hash[k][x][y]=1;while( first<end ){if( map[q[first].flag][q[first].x][q[first].y]=='P' )return true;for( int i=0;i<4;i++ ){int dx=q[first].x + d[i][0];int dy=q[first].y + d[i][1];int flag=q[first].flag;int time=q[first].time-1;if( judge( dx,dy,flag,time )&&!hash[flag][dx][dy] ){if( map[flag][dx][dy]!='#' ){if( map[flag][dx][dy]=='P' ){ return true;}end=push( dx,dy,time,flag,end );}hash[flag][dx][dy]=1;if( map[flag][dx][dy]=='#'&&!hash[(flag+1)%2][dx][dy])if(map[( flag +1 )%2][dx][dy]!='*'&&map[(flag +1 )%2][dx][dy]!='#' ){if( map[( flag +1 )%2][dx][dy]=='P' ) return true;hash[( flag+1 )%2][dx][dy]=1;end=push( dx,dy,time,(flag+1)%2,end ) ;  }}     }first++;       } return false;    
}
int main()
{int n,T,X,Y,K;scanf( "%d",&n );while( n-- ){memset( map,0,sizeof( map ) );scanf( "%d%d%d",&N,&M,&T );for( int k=0;k<2;k++ )for( int i=1;i <= N; i++ ){scanf( "%s",map[k][i]+1 );     } getxy( X,Y,K );if( BFS( X,Y,K,T ) ) printf( "YES\n" );else printf( "NO\n" );     }   
}

 代码2：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
class Node
{
public:
int floor,x,y,time;    
};
Node queue[1024];
char map[2][14][14];
int d[4][2]={ 0,1,1,0,0,-1,-1,0  };
bool BFS( int time )
{
int first = 0 , end = 0;
    Node t;
    t.x = 1;
    t.y = 1;
    t.time = 0;
    t.floor = 0;
    queue[end] = t;
    end++;
    map[0][1][1] = '*';
while( first < end )
    {
          t = queue[first];
int T = t.time+1;
if(time>=T) 
        {
for( int i = 0; i< 4 ; i++ )
              {
int dx = t.x + d[i][0];
int dy = t.y + d[i][1];    
if( map[t.floor][dx][dy]=='#'||map[t.floor][dx][dy]=='.'||map[t.floor][dx][dy]=='P' )
               {
//            if( t.floor==1 )       printf( "%d %d %d time=%d\n",t.floor,dx ,dy ,t.time);
                  if( map[t.floor][dx][dy]=='P' )
                  {
return true;         
                  }        
if( map[t.floor][dx][dy]=='#' )
                  {
if(map[(t.floor+1)%2][dx][dy]!='*'&&map[(t.floor+1)%2][dx][dy]!='#')
                      {    
//                         printf( "%d %d %d time=%d\n",t.floor,dx ,dy ,T);
                        
if( map[(t.floor+1)%2][dx][dy]=='P' )
                         {
return true;         
                         }
else
                         {                            
                            queue[end].time = T;
                            queue[end].x = dx;
                            queue[end].y = dy;
                            queue[end].floor = (t.floor+1)%2;
                            map[(t.floor+1)%2][dx][dy]='*';
                            end++;        
                         }    
                        map[t.floor][dx][dy] = '*';
                      }
                    }
if( map[t.floor][dx][dy]=='.' )
                  {
                        map[t.floor][dx][dy]='*';
                        queue[end].time = T;
                        queue[end].x = dx;
                        queue[end].y = dy;
                        queue[end].floor = t.floor;
                        end++;        
                  }
               }
            }
        }
        first++;
    }
return false;
}
int main( )
{
int Case,n,m,time;
while( scanf( "%d",&Case )==1 )
    {
while( Case -- )
       {
          memset( map , 0 ,sizeof( map ) );
          scanf( "%d%d%d",&n , &m ,&time );
for( int i = 0; i<2 ; i++ )
          {
for( int j=1 ; j<= n ; j++ )
                 scanf( "%s",map[i][j]+1 );        
          }
if( BFS( time ) )
           printf( "YES\n" );
else  printf( "NO\n" );        
       }    
    }
return 0;    
}