题目
给定一张 的地图，地图中有 个男孩， 个女孩和 个鬼。
字符 . 表示道路，字符 X 表示墙，字符 M 表示男孩的位置，字符 G 表示女孩的位置，字符 Z 表示鬼的位置。
男孩每秒可以移动 个单位距离，女孩每秒可以移动 个单位距离，男孩和女孩只能朝上下左右四个方向移动。
每个鬼占据的区域每秒可以向四周扩张 个单位距离，并且无视墙的阻挡，也就是在第 秒后所有与鬼的曼哈顿距离不超过 的位置都会被鬼占领。
注意： 每一秒鬼会先扩展，扩展完毕后男孩和女孩才可以移动。
求在不进入鬼的占领区的前提下，男孩和女孩能否会合，若能会合，求出最短会合时间。
输入格式
第一行包含整数 ，表示共有 组测试用例。
每组测试用例第一行包含两个整数 和 ，表示地图的尺寸。
接下来 行每行 个字符，用来描绘整张地图的状况。（注意：地图中一定有且仅有 个男孩， 个女孩和 个鬼）
输出格式
每个测试用例输出一个整数 ，表示最短会合时间。
如果无法会合则输出 。
每个结果占一行。
数据范围
输入样例：
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
解题
方法一：BFS
思路
BFS模板题，但本题的设计比较复杂，有几个细节需要注意：
-
鬼(
'Z')每秒行动的范围是('z')：z zzz zzZzz zzz z -
鬼无视墙的阻挡：直接理解成鬼能往墙上走就行了（反正鬼和墙都能挡人）。
-
男孩每秒可以移动 个单位距离不是指只能向上下左右其中一个方向移动 个单位，而是指男孩每轮可以进行 次距离为 的移动。
代码
#include <iostream>
#include <limits>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 810;
// ⬇️⬆️➡️⬅️
const int DIRS4[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// ↖️⬆️↗️⬅️➡️↙️⬇️↘️
const int DIRS8[][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int t, n, m;
char g[N][N];
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
queue<PII> oni_que, boy_que, girl_que;
for (int i = 0; i < n; ++i) {
cin.ignore(numeric_limits<streamsize>::max(), '\n');
for (int j = 0; j < m; ++j) {
char c;
scanf("%c", &c);
if (c == 'Z') oni_que.push({i ,j});
else if (c == 'M') boy_que.push({i, j});
else if (c == 'G') girl_que.push({i, j});
g[i][j] = c;
}
}
int step = 0; // 时间(轮数)
while (!oni_que.empty() && !boy_que.empty() && !girl_que.empty()) {
++step;
int sz = oni_que.size();
// 鬼行动
while (sz--) {
auto pr = oni_que.front();
oni_que.pop();
int x = pr.first, y = pr.second;
for (auto& DIR : DIRS8) {
int nx = x + DIR[0], ny = y + DIR[1];
// 不能越界 不能走之前走过的地方(剪枝)
if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] != 'Z') {
g[nx][ny] = 'Z';
oni_que.push({nx, ny});
}
}
for (auto& DIR : DIRS4) {
int nx = x + DIR[0] * 2, ny = y + DIR[1] * 2;
if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] != 'Z') {
g[nx][ny] = 'Z';
oni_que.push({nx, ny});
}
}
}
// 男孩行动三次
for (int k = 0; k < 3; ++k) {
sz = boy_que.size();
while (sz--) {
auto pr = boy_que.front();
boy_que.pop();
int x = pr.first, y = pr.second;
if (g[x][y] == 'Z') continue;
for (auto& DIR : DIRS4) {
int nx = x + DIR[0], ny = y + DIR[1];
// 不能越界 不能走鬼或者墙上 不能走之前走过的地方(剪枝)
if (nx < 0 || nx >= n || ny < 0 || ny >= m ||
g[nx][ny] == 'X' || g[nx][ny] == 'Z' || g[nx][ny] == 'M') continue;
// 如果遇到女孩 直接输出当前轮次 结束
if (g[nx][ny] == 'G') {
printf("%d\n", step);
goto out;
}
g[nx][ny] = 'M';
boy_que.push({nx, ny});
}
}
}
sz = girl_que.size();
// 女孩行动一次
while (sz--) {
auto pr = girl_que.front();
girl_que.pop();
int x = pr.first, y = pr.second;
if (g[x][y] == 'Z') continue;
for (auto& DIR : DIRS4) {
int nx = x + DIR[0], ny = y + DIR[1];
// 不能越界 不能走鬼或者墙上 不能走之前走过的地方(剪枝)
if (nx < 0 || nx >= n || ny < 0 || ny >= m ||
g[nx][ny] == 'X' || g[nx][ny] == 'Z' || g[nx][ny] == 'G') continue;
// 如果遇到男孩 直接输出当前轮次 结束
if (g[nx][ny] == 'M') {
printf("%d\n", step);
goto out;
}
g[nx][ny] = 'G';
girl_que.push({nx, ny});
}
}
}
// 遇不到 输出-1 结束
puts("-1");
out:;
}
return 0;
}
评论区