可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。
Input输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小N*M（1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况，后N*M表示迷宫第二层的布置情况。Output如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。Sample Input
1
5 5 14
S*#*.
.#...
.....
****.
...#. ..*.P
#.*..
***..
...*.
*.#..
Sample Output
YES
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef long long LL;
const LL maxn = 13;
const int inf = 1<<30;//每一次乘以2
int N, M, T;
int vis[4][maxn][maxn]; //vis为到达该点的最短时间, -1为不可达, inf为未走过
char mp[4][maxn][maxn]; //地图[层数][x][y];
int f[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //前后左右, 上下
bool check(int cx, int cy)
{
if(cx>0&&cx<=N&&cy>0&&cy<=M) return 1;
else return 0;
}
bool Dfs(int x, int y, int z, int t)
{
if(mp[z][x][y]=='P') return true;
if(t==T) return false;
int cx, cy, cz;
for(int i = 0; i < 4; i++)
{
cx = x+f[i][0], cy = y+f[i][1], cz = z;
if(check(cx, cy) && vis[cz][cx][cy]>t+1)
{
if(mp[cz][cx][cy]=='.' || mp[cz][cx][cy]=='P')
{
vis[cz][cx][cy] = t+1; //改变时间戳
if(Dfs(cx, cy, cz, t+1)) return true;
}
else if(mp[cz][cx][cy]=='#') //碰见传送门必传送
{
vis[cz][cx][cy] = t+1; //改变时间戳
cz = (z==1)?2:1;
if(mp[cz][cx][cy]=='#' || mp[cz][cx][cy]=='*')//*和#都不能通过
{
vis[cz][cx][cy] = vis[z][cx][cy] = -1; //设置为不可达
continue;
}
vis[cz][cx][cy] = t+1;
if(Dfs(cx, cy, cz, t+1)) return true; //不花费时间
}
}
}
return false;
}
int main()
{
int C;
cin >> C;
while(C--)
{
ms(vis, 0); ms(mp, 0);
cin >> N >> M >> T;
for(int k = 1; k <= 2; k++)
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
{
cin >> mp[k][i][j];
vis[k][i][j] = inf; //初始化
}
//开始深搜
vis[1][1][1] = 0;
if(Dfs(1, 1, 1, 0)) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}