hdu 2102 A计划

Posted on | In |

可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。

Input
输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小NM（1 <= N,M <=10)。T如上所意。接下去的前NM表示迷宫的第一层的布置情况，后NM表示迷宫第二层的布置情况。

Output
如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
1
5 5 14
S*#*.
.#...
.....
****.
...#.

..*.P
#.*..
***..
...*.
*.#..

Sample Output

YES

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
#define  MAX 10
int m,n,lim;
struct node{
	int x,y,z,step;
	node(int xx,int yy,int zz,int ss):x(xx),y(yy),z(zz),step(ss){
	} 
	node(){
		
	}
};
char grid[MAX][MAX][2]; 
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int main(){
	int cases;
	//freopen("12.txt","r",stdin);
	cin>>cases;
	while(cases--){
		int flag=0;
		
		
		memset(grid,'*',sizeof(grid));
		cin>>m>>n;
		cin>>lim;
		for(int k=0;k<2;k++)
		{
				for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			cin>>grid[i][j][k];
		} 
		} 	
			
		}

		queue<node> q;
		q.push(node(0,0,0,0));
		while(!q.empty()){
			node t=q.front();
			q.pop();
			if(grid[t.x][t.y][t.z]=='P') {
				flag=1;
				break;
				
			}
			if(grid[t.x][t.y][t.z]=='*') {
				continue;
			}
			grid[t.x][t.y][t.z]='*';
			for(int i=0;i<4;i++){
				int nx=t.x+dir[i][0];
				int ny=t.y+dir[i][1];
				int nz=t.z;
				if(t.step+1>lim) {
				continue;
				}
                //!!
			if(nx<0||nx>=m||ny<0||ny>=n) continue;
				if(grid[nx][ny][nz]=='*') continue;

				if(grid[nx][ny][nz]=='#') {
					//!!
					grid[nx][ny][nz]='*';
						nz=1-nz;
				if(grid[nx][ny][nz]=='#' || grid[nx][ny][nz]=='*') {
                    grid[nx][ny][nz]= grid[nx][ny][1-nz] = '*';
                    continue;
                }
                
				}				
				q.push(node(nx,ny,nz,t.step+1));
				
			} 
			
		}
		
		if(flag==1)	cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
		
	}
	
	
	
}