HDU3085 『神威灵装三番(Nightmare)II』

今天没有魔改题目,只是把题目翻译成中文而已(逃

题目大意:

从前有一个地图,地图里有一对男女和俩鬼。男的移动速度3格/s,女的1格/m。

鬼很可怕,每秒可以向四周扩散两个单位距离并且自带穿墙挂。也就是说k秒后所有与鬼距离曼哈顿不超过2k的位置都会被鬼占领。

求不被鬼吃掉的前提下男女几步能见面。

思路:

不难想到双向bfs。分别从男女起始位置开始轮流bfs,男每次bfs3次(腿长),女1次。

在bfs中如果发现卧槽这个位置对方来过,那么就相遇了输出结果。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#define MAXN 850
using namespace std;
int n, m, Case, step;
char map[MAXN][MAXN];
struct dot
{
	int x, y;
} otk, onn, oni[2];
queue <dot> q[2], que;
int fx[4] = {1, 0, -1, 0};
int fy[4] = {0, 1, 0, -1};
void shyokika()
{
	while(!q[0].empty()) q[0].pop();
	while(!q[1].empty()) q[1].pop();
	while(!que.empty()) que.pop();
	step = 0;
}
bool dekinai(dot a)
{
	if(a.x > n || a.y > m || a.x < 1 || a.y < 1 || map[a.x][a.y] == 'X' || map[a.x][a.y] == '\0') return 1;
	for(int i = 0;i <= 1;i++)
		if(abs(a.x - oni[i].x) + abs(a.y - oni[i].y) <= step*2) return 1;
	return 0;
}
bool bfs(int u, int times, char start, char end)
{
	dot a, b;
	while(times--)
	{
		que = q[u];
		while(!que.empty())
		{
			a = que.front();
			que.pop();
			q[u].pop();
			if(dekinai(a)) continue;
			for(int i = 0;i < 4;i++)
			{
				b = a;
				b.x += fx[i]; b.y += fy[i];
				if(dekinai(b) || map[b.x][b.y] == start) continue;
				if(map[b.x][b.y] == end) return 1;
				q[u].push(b);
				map[b.x][b.y] = start;
			}
		}
	}
	return 0;
}
int tokeru()
{
	bool otoko, onna;
	q[0].push(otk);
	q[1].push(onn);
	while(!q[0].empty() && !q[1].empty())
	{
		step++;
		otoko = bfs(0, 3, 'M', 'G');
		onna  = bfs(1, 1, 'G', 'M');
		if(otoko || onna) return step;
	}
	return -1;
}
int main()
{
	scanf("%d", &Case);
	while(Case--)
	{
		//memset(map, 'X', sizeof(map));
		int k = 0;
		scanf("%d%d", &n, &m);
		for(int i = 1;i <= n;i++)
		{
			scanf("%s", map[i]+1);
			for(int j = 1;j <= m;j++)
			{
				if(map[i][j] == 'M'){otk.x = i;otk.y = j;}
				if(map[i][j] == 'G'){onn.x = i;onn.y = j;}
				if(map[i][j] == 'Z'){oni[k].x = i;oni[k++].y = j;}
			}
		}
		shyokika();
		printf("%d\n", tokeru());
	}
}

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00