HDOJ 題目2102 A計劃（BFS）

A計劃

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10858 Accepted Submission(s): 2646


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

1
5 5 14
S*#*.
.#...
.....
****.
...#.

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

Sample Output

YES

Source HDU 2007-6 Programming Contest
Recommend xhd | We have carefully selected several similar problems for you: 1180 1175 1240 1254 1026 ac代碼

#include
#include
#include
#include
#include
#include
using namespace std;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int n,m,T;
char map[2][1010][1010];
int v[2][1010][1010];
struct s
{
	int x,y,step,z;
}a,temp;
int sx,sy,sz;
int jud(struct s a)
{
	if(a.x<0||a.x>=n||a.y<0||a.y>=m)
		return 0;
	if(map[a.z][a.x][a.y]=='*'||map[a.z][a.x][a.y]=='#')
		return 0;
	if(v[a.z][a.x][a.y])
		return 0;
	if(a.step>T)
		return 0;
	return 1;
}
int bfs()
{
	a.x=sx;
	a.y=sy;
	a.z=sz;
	a.step=0;
	queueq;
	v[sz][sx][sy]=1;
	q.push(a);
	while(!q.empty())
	{
		a=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			temp.x=a.x+dx[i];
			temp.y=a.y+dy[i];
			temp.step=a.step+1;
			if(map[a.z][temp.x][temp.y]=='#')
			{
				if(a.z)
					temp.z=0;
				else
					temp.z=1;
			}
			else
			{
				temp.z=a.z;
				//temp.step=a.step+1;
			}
			if(jud(temp))
			{
				if(map[temp.z][temp.x][temp.y]=='P')
				{
					return 1;
				}
				v[temp.z][temp.x][temp.y]=1;
				q.push(temp);
			}
		}
	}
	return 0;
}
int main()
{
	int t;
	//scanf("%d",&t);
	cin>>t;
	while(t--)
	{
		int i,j,k;
		scanf("%d%d%d",&n,&m,&T);
		for(k=0;k<2;k++)
		{
			for(i=0;i