HDU 2102 A 계획 (DFS)

A 계획
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16220    Accepted Submission(s): 4084
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 #.*.. ***.. ...*. *.#..
   
   
   
   

Sample Output

   
   
   
   

    
    
    
    YES
   
   
   
   

Source
HDU 2007-6 Programming Contest
Recommend
xhd   |   We have carefully selected several similar problems for you:  2717 1429 1195 2579 1401 
문제 풀이: 두 개의 그림 을 드 리 겠 습 니 다. 그림 의 표 지 는 문제 에서 말 한 바 와 같 습 니 다. 이 두 그림 은 연 결 된 것 일 수도 있 고 점프 할 수 있 습 니 다. t 시간 안에 (0, 0,) 에서 'P' 의 위치 에 도착 할 수 있 는 지 물 어보 세 요.
 DFS 한번 훑 어보 고... BFS 도...
주의: 입력 한 두 그림 사이 에 빈 칸 이 있 습 니 다.
AC 코드:

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
int vis[2][11][11];
char map[2][11][11];
int n,m,times,flag;

int check(int next_x,int next_y)
{
	if(next_x>=0&&next_x<n&&next_y>=0&&next_y<m)
	return 1;
	else return 0;
}


int dfs(int x,int y,int z,int t)
{
	if(map[z][x][y]=='P')
	{
		if(t<=times)
		return 1;
		else return 0;
	}
	
	for(int i=0; i<4; i++)
	{
		int next_x=x+dx[i];
		int next_y=y+dy[i];
		if(check(next_x,next_y)&&!vis[1-z][next_x][next_y]&&map[z][next_x][next_y]=='#'&&map[1-z][next_x][next_y]!='*'&&map[1-z][next_x][next_y]!='#')
		{
			vis[1-z][next_x][next_y]=1;
			if(dfs(next_x,next_y, 1-z ,t+1))  
			return 1;
			vis[1-z][next_x][next_y]=0;
		}
		else 
		 if(check(next_x,next_y)&&!vis[z][next_x][next_y]&&map[z][next_x][next_y]!='#'&&map[z][next_x][next_y]!='*')
		 {
		 	vis[z][next_x][next_y]=1;
		 	if(dfs(next_x,next_y, z ,t+1))
		 	  return 1;
		 	vis[z][next_x][next_y]=0;
		 }
	}
	return 0;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,×);
		memset(vis,0,sizeof(vis));
		memset(map,0,sizeof(map));
		for(int i=0;i<2;i++)
		{
			getchar();
			for(int j=0;j<n;j++)
			{
				for(int k=0;k<m;k++)
				
					scanf("%c",&map[i][j][k]);//          。。。WA   。。。   
					getchar();
				
			}
		}
		vis[0][0][0]=1;
		if(dfs(0,0,0,0))
		{
			printf("YES
");
		}
		else puts("NO");
	}
	return 0;
}