A计划
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13301 Accepted Submission(s):
3284
Problem Description
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在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表示迷宫第二层的布置情况。
<= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况，后N*M表示迷宫第二层的布置情况。
Output
如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。
Sample Input
1
5 5 14
S*#*.
.#...
.....
****.
...#.
..*.P
#.*..
***..
...*.
*.#..
Sample Output
YES
注意：1、如果两层的同一个位置都是#或者#对应另一层的位置是*都不能通过。
2、从一层到另一层只能通过时空传送机
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
char map[11][11][11];
int vis[11][11][11];
int n,m,t;
struct node
{
int x,y,z;
int time;
friend bool operator < (node a,node b)
{
return a.time>b.time;
}
};
int judge(int r,int c,int d)
{
if(r<0||r>=2||c<0||c>=n||d<0||d>=m)
return 0;
if(map[r][c][d]=='*'||vis[r][c][d])
return 0;
return 1;
}
int bfs()
{
int i,j;
int move[4][2]={0,1,0,-1,1,0,-1,0};
priority_queue<node>q;
node beg,end;
beg.x=0;
beg.y=0;
beg.z=0;
beg.time=0;
q.push(beg);
vis[0][0][0]=1;
while(!q.empty())
{
end=q.top();
q.pop();
if(map[end.x][end.y][end.z]=='P')
{
if(end.time<=t)
return 1;
return 0;
}
if(map[end.x][end.y][end.z]=='#')
{
beg.x=1-end.x;
beg.y=end.y;
beg.z=end.z;
beg.time=end.time;
if(judge(beg.x,beg.y,beg.z)&&map[beg.x][beg.y][beg.z]!='#')
{
q.push(beg);
}
}
else
for(i=0;i<4;i++)
{
beg.x=end.x;
beg.y=end.y+move[i][0];
beg.z=end.z+move[i][1];
if(judge(beg.x,beg.y,beg.z))
{
vis[beg.x][beg.y][beg.z]=1;
beg.time=end.time+1;
q.push(beg);
}
}
}
return 0;
}
int main()
{
int i,j,k,o;
scanf("%d",&o);
while(o--)
{
memset(vis,0,sizeof(vis));
scanf("%d%d%d",&n,&m,&t);
for(k=0;k<2;k++)
{
for(i=0;i<n;i++)
scanf("%s",map[k][i]);
}
if(bfs()) printf("YES\n");
else printf("NO\n");
}
return 0;
}