HDU - 항 저 우 전기 - 2102 - A 계획 - 심층 검색

A 계획
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7720    Accepted Submission(s): 1853
Problem Description
불쌍 한 공 주 는 마왕 에 게 한 번 씩 납 치 돼 기사 들 에 게 구 조 된 후 불행 하 게 도 그녀 는 다시 생명의 시련 에 직면 하 게 되 었 습 니 다.마왕 은 T 시 에 공 주 를 잡 아 먹 을 것 이 라 고 메 시 지 를 보 냈 습 니 다. 공주 의 고 기 를 먹 어도 오래 살 수 있다 는 소문 을 믿 었 기 때 문 입 니 다.늙 은 왕 은 마음 이 급 하여 천하 의 용 사 를 불 러 공 주 를 구 하 겠 다 고 고 했 습 니 다.하지만 공 주 는 익숙 해 졌 습 니 다. 지 용의 기사 LJ 가 구 해 낼 수 있 을 거 라 고 믿 었 습 니 다.
현재 밀정 에 따 르 면 공 주 는 2 층 미궁 에 갇 혀 있다. 미궁 의 입 구 는 S (0, 0, 0) 이 고 공주 의 위 치 는 P 로 표시 하 며 시공 전송 기 는\# 로 표시 하고 벽 은 * 로 표시 하 며 평지 용 으로 표시 한다.기사 들 은 시공 전송 기 에 들 어가 면 다른 층 의 상대 적 인 위치 로 옮 겨 지지 만, 옮 겨 진 위치 가 벽 이 라면 기사 들 은 부 딪 혀 죽는다.기사 들 은 1 층 에서 한 칸 씩 이동 하 는 데 1 시간 이 걸린다.층 간 의 이동 은 시공 전송 기 를 통과 할 수 있 을 뿐 어떠한 시간 도 필요 없다.
 
Input
입력 한 첫 줄 C 는 모두 C 개의 테스트 데 이 터 를 표시 하고 테스트 데이터 의 앞 줄 마다 세 개의 정수 N, M, T 가 있다.N, M 미궁 의 크기 N * M (1 < = N, M < = 10). T 는 위 와 같다. 이 어 진 전 N * M 은 미궁 의 1 층 배치 상황 을 나타 내 고, 후 N * M 은 미궁 2 층 배치 상황 을 나타 낸다.
 
Output
기사 들 이 T 시간 에 공 주 를 찾 을 수 있다 면 'YES' 를 출력 하고 그렇지 않 으 면' NO '를 출력 한다.
 
Sample Input

 
   

     1 5 5 14 S*#*. .#... ..... ****. ...#. ..*.P #.*.. ***.. ...*. *.#.. 
   
 
  

#include 
#include 
#include 
using namespace std;
int n,m,t,xx[4][2]={{1,0},{0,1},{-1,0},{0,-1}},xp,yp,visit[2][11][11];  //xp、yp     
char map[2][11][11];  //     ，     
void input(int x)  //    ，       ，             --！
{
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            visit[x][i][j]=1;  //     visit  
            cin>>map[x][i][j];
            if(map[x][i][j]=='P')xp=i,yp=j;  //         
        }
}
int ABS(int a)  //    
{
    return a>0?a:-a;
}
bool dfs(int X,int Y,int Z,int step)
{
    int i,j,k,l,x,y,z;
    if(map[Z][X][Y]=='P')return 1;  //    
    if(step==0)return 0;  //    
    x=ABS(X-xp)+ABS(Y-yp);  //x               
    if(x>step)return 0;  //      
    for(i=0;i<4;i++)
    {
        x=X+xx[i][0];
        y=Y+xx[i][1];
        z=Z;
        if(x>=0&&y>=0&&x<n&&y<m&&visit[z][x][y]&&map[z][x][y]!='*')  //   ，visit     ，    *
        {
            if(map[z][x][y]=='#')z=1-z;  //   #        
            visit[z][x][y]=0;
            if(map[z][x][y]!='#'&&map[z][x][y]!='*'&&dfs(x,y,z,step-1))return 1;  //    * #，*   ，#     
            visit[z][x][y]=1;
        }
    }
    return 0;
}
int main (void)
{
    int T,i,j,k,l;
    cin>>T;
    while(T--&&cin>>n>>m>>t)
    {
        input(0);
        input(1);
        if(dfs(0,0,0,t))cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

그냥 깊 은 검색 이지 만 주의해 야 할 것 이 있 습 니 다. 문 제 는 t 시간 안에 도착 하 는 것 입 니 다. 친, 그리고 가지치기 문제 도 있 습 니 다. 인형 으로 가 지 를 자 르 지 않 아 도 됩 니 다. 그리고 판단 조건 은 어느 층 인지 구분 해 야 합 니 다. 가장 좋 은 것 은 바로 P 와 같 습 니 다.