HDU 2102 (검색 문제, BFS)

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

#include #include using namespace std; #define N 15 struct node { int x,y,time; int l; }; char a[2][N][N]; int mark[2][N][N]; int dis[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; int T; void BFS() { queue q; node s1,s2; s1.x=1; s1.y=1; s1.time=T; s1.l=0; q.push(s1); int i; memset(mark,0,sizeof(mark)); mark[0][s1.x][s1.y]=1; while(!q.empty()) { s1=q.front(); q.pop(); for(i=0;i<4;i++) { s2=s1; s2.x+=dis[i][0]; s2.y+=dis[i][1]; if(mark[s2.l][s2.x][s2.y]==0 && a[s2.l][s2.x][s2.y]!='*') { if(a[s2.l][s2.x][s2.y]=='#') { if(s2.l) s2.l=0; else s2.l=1; if(mark[s2.l][s2.x][s2.y]) continue; } s2.time--; mark[s2.l][s2.x][s2.y]=1; if(s2.time<0) { printf("NO/n"); return; } if(a[s2.l][s2.x][s2.y]=='P') { printf("YES/n"); return; } q.push(s2); } } } printf("NO/n"); } int main() { int t,n,m,i,j,k; scanf("%d",&t); while(t--) { scanf("%d%d%d%*c",&n,&m,&T); memset(a,'*',sizeof(a)); for(k=0;k<2;k++) { for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%c",&a[k][i][j]); } getchar(); } if(k!=1) getchar(); } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(a[0][i][j]=='#' && a[1][i][j]=='*') a[0][i][j]='*'; else if(a[0][i][j]=='*' && a[1][i][j]=='#') a[1][i][j]='*'; else if(a[0][i][j]=='#' && a[1][i][j]=='#') a[0][i][j]=a[1][i][j]='*'; } } BFS(); } return 0; }