题目描述
给定一张N*M的地图,地图中有1个男孩,1个女孩和2个鬼。
字符“.”表示道路,字符“X”表示墙,字符“M”表示男孩的位置,字符“G”表示女孩的位置,字符“Z”表示鬼的位置。
男孩每秒可以移动3个单位距离,女孩每秒可以移动1个单位距离,男孩和女孩只能朝上下左右四个方向移动。
每个鬼占据的区域每秒可以向四周扩张2个单位距离,并且无视墙的阻挡,也就是在第k秒后所有与鬼的曼哈顿距离不超过2k的位置都会被鬼占领。
注意: 每一秒鬼会先扩展,扩展完毕后男孩和女孩才可以移动。
求在不进入鬼的占领区的前提下,男孩和女孩能否会合,若能会合,求出最短会合时间。
输入格式
第一行包含整数T,表示共有T组测试用例。
每组测试用例第一行包含两个整数N和M,表示地图的尺寸。
接下来N行每行M个字符,用来描绘整张地图的状况。(注意:地图中一定有且仅有1个男孩,1个女孩和2个鬼)
输出格式
每个测试用例输出一个整数S,表示最短会合时间。
如果无法会合则输出-1。
每个结果占一行。
数据范围
1<n,m<800
样例
输出样例:
3
5 6
XXXXXX
XZ..ZX
XXXXXX
M.G...
......
5 6
XXXXXX
XZZ..X
XXXXXX
M.....
..G...
10 10
..........
..X.......
..M.X...X.
X.........
.X..X.X.X.
.........X
..XX....X.
X....G...X
...ZX.X...
...Z..X..X
输出样例:
1
1
-1
学习自:Dr.Lo
https://www.acwing.com/solution/acwing/content/2890/
不同点:鬼走的步数400步为极限
C++ 代码
#include<iostream>
#include<queue>
#include<cstring>
//该题我的疑惑点在于男孩女孩可不可以不走这一秒他们应该走的步数
struct kk
{
int x, y, pay;
};
std::queue<struct kk>boy, girl, ghost;
int N, M, T;
char mp[852][852] = { {} };
int visit[852][852] = { {} };
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int BFS()
{
memset(visit, 0, sizeof(visit));
int cx = 420, yr = -1;//鬼每次扩散两步的长度范围,所以800的方格,以鬼再(1,1)的极限位置
//仅经过400步即可占领全图,这里420怕计算错误取了个比400还大的值,避免400步之后鬼还没占领全图
struct kk tmp;
while (cx--)
{
if (!ghost.empty())
yr = ghost.front().pay;
while (!ghost.empty() && ghost.front().pay < yr + 2)
{
tmp = ghost.front();
ghost.pop();
for (int i = 0; i < 4; i++)
{
int now_x = tmp.x + dir[i][1], now_y = tmp.y + dir[i][0], now_pay = tmp.pay + 1;
if (!visit[now_y][now_x] && '#' != mp[now_y][now_x])
visit[now_y][now_x] = 1, mp[now_y][now_x] = 'X', ghost.push({ now_x,now_y,now_pay });
//将鬼可以占领到的地方都设为X,代表墙,不能行走,若该位置男孩或女孩曾经到达过,再次遍历到
//该位置时就是非法位置,跳过
}
}
if (!boy.empty())
yr = boy.front().pay;
while (!boy.empty() && boy.front().pay < yr + 3)
{
tmp = boy.front();
boy.pop();
if ('M' != mp[tmp.y][tmp.x])continue;
for (int i = 0; i < 4; i++)
{
int now_x = tmp.x + dir[i][1], now_y = tmp.y + dir[i][0], now_pay = tmp.pay + 1;
if ('M' == mp[now_y][now_x])continue;
int kj = now_pay % 3 ? 1 : 0;
if ('G' == mp[now_y][now_x])return now_pay / 3 + kj;//男孩一秒走三步,若走了三步则一秒就完成了,
//而四步却要两秒,kj的作用就在这里
if ('.' == mp[now_y][now_x])
mp[now_y][now_x] = 'M', boy.push({ now_x,now_y,now_pay });
//将男孩接下来可以到达的位置设为M,若这一步遇到女孩可以到达的位置,则返回经过了几秒
//因为要走三步,男孩可以这样走 (左走一步,右走一步,再左走一步),相当于一步,而第二秒时
//就可以回到原来的位置,所以原先走到过的位置应该保留,除非被鬼占领了
}
}
if (!girl.empty())
yr = girl.front().pay;
while (!girl.empty() && girl.front().pay < yr + 1)
{
tmp = girl.front();
girl.pop();
if ('G' != mp[tmp.y][tmp.x])continue;
for (int i = 0; i < 4; i++)
{
int now_x = tmp.x + dir[i][1], now_y = tmp.y + dir[i][0], now_pay = tmp.pay + 1;
if ('M' == mp[now_y][now_x])return now_pay;
if ('G' == mp[now_y][now_x])continue;
if ('.' == mp[now_y][now_x])mp[now_y][now_x] = 'G', girl.push({ now_x,now_y,now_pay });
}
}
}
return -1;
}
int main(void)
{
std::ios_base::sync_with_stdio(false);
std::cin >> T;
while (T--)
{
std::queue<struct kk>().swap(boy);
std::queue<struct kk>().swap(girl);
std::queue<struct kk>().swap(ghost);
std::cin >> N >> M;
for (int i = 0; i <= M + 1; i++)mp[0][i] = mp[N + 1][i] = '#';
//设置为#的作用,当鬼向它占领的格子向四周蔓延开来时,mp中是'X'的也要入队
//虽然它不能改该位置的数据了,(已经是X了),但是下次广搜时还是要根据位置
//向四周扩散,为了避免广搜出界,所以设为#,代表这是边界,而不是设置为’X'
//与墙的数值区分开来
for (int i = 0; i <= N + 1; i++)mp[i][0] = mp[i][M + 1] = '#';
for (int i = 1; i <= N; i++)
{
for (int m = 1; m <= M; m++)
{
std::cin >> mp[i][m];
if ('G' == mp[i][m])girl.push({ m,i,0 });
else if ('Z' == mp[i][m])ghost.push({ m,i,0 }), mp[i][m] = 'X';
else if ('M' == mp[i][m])boy.push({ m,i,0 });
}
}
if (boy.front().x == girl.front().x && boy.front().y == girl.front().y)
{
std::cout << "0" << "\n";
continue;
}
else std::cout << BFS() << "\n";
}
return 0;
}