优先bsf rescue

Submit Status

Description

Input

Output

Sample Input

Sample Output

Hint

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

Hint

Description

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

Input

First line contains two integers stand for N and M.

Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend.

Process to the end of the file.

Output

For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."

Sample Input

7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........

Sample Output

代码虽然自己写的 但是优先bfs是看的别人的QAQ

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
char prison[205][205];
bool visited[205][205];
int n, m;
int d[4][2] = { 0,1,1,0,-1,0,0,-1 };
struct node
{
	int x, y, step;
	friend bool operator < (node a, node b)
	{
		return a.step>b.step;
	}

};
node angel;

void bfs(int x,int y)
{
	node s, e;
	s.x = x;
	s.y = y;
	s.step = 0;
	priority_queue<node>q;
	q.push(s);
	while(!q.empty())
	{
		e = q.top();
		q.pop();
		if (prison[e.x][e.y] == 'a')
		{
			printf("%d\n", e.step);
			return;
		}
		for(int i=0;i<4;i++)
		{
			s.x = e.x + d[i][0];
			s.y = e.y + d[i][1];
			s.step = e.step + 1;
			if (s.x >=0 && s.x<n && s.y>=0 && s.y<m && visited[s.x][s.y]==false && prison[s.x][s.y]!='#')
			{
				if (prison[s.x][s.y] == 'x') { s.step += 1; }
				visited[s.x][s.y] = true;
				q.push(s);
			}
		}
		
	}
	printf("Poor ANGEL has to stay in the prison all his life.\n");
	return;
};
int main()
{
	
	while(~scanf("%d %d", &n, &m))
	{
		getchar();
		node strat;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				scanf("%c", &prison[i][j]);
				if(prison[i][j]=='a')
				{ 
					angel.x = i;
					angel.y = j;
				}
				if(prison[i][j]=='r')
				{
					strat.x = i;
					strat.y = j;
				}
			}
			getchar();
		}
		memset(visited, false, sizeof(visited));
		bfs(strat.x, strat.y);
	}
	return 0;
}

//by suwst tp