hdoj 2102 A计划

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时刻。层间的移动只能通过时空传输机，且不需要任何时间。

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

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
");
		else printf("NO
");
	}
	return 0;
}