优先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

13
代码虽然自己写的 但是优先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
全部评论

相关推荐

就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
求offer的大角牛:不吃香菜
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务