题解：P10487 Nightmare II
切入点：男生和女友会同时的进行移动，所以考虑同时移动并且相聚时间最短。考虑多源点广搜。
（当然直接按照题目本身的表述意思就是双向广搜。）
- 多起点出发的时候，可以直接考虑男生和女友走的相同时间的队列扩展。
- 但是需要注意的是，本题因为男生会走三步，但是女友只能走一步，所以可以考虑先创建一个临时的队列，每次将男生走三步的所有点在临时队列之中扩展完成之后放入原队列，但是这样显然过于麻烦，并且最后的结构体之中需要多创建一个时间编号。
- 所以最终可以直接将男生和女友分开创建一个队列，也就是双向广搜的基本操作。如果每次二者都是移动一步，一个队列的写法也不错。
考虑创建开两个队列，分别存储男生和女友的移动点。
注意点
- 因为鬼魂的移动是按照时间记录步数的，比如鬼魂移动两步，可以先往右再往上，也可以先往上后往右，其实表述起来就是二者之间的曼哈顿距离小于两倍时间。所以记录一个全局的时间节点。
- 每次扩展的时候，男生和女友同时移动，相当于在一秒的时间单位内，先移动男生的所有上一层的节点，队列之中所有节点，扩展三次，后移动女友的所有上一层节点，扩展一次。当然交换二者之间的顺序关系也可以。
- 关于标记，采用三维的方式，最后一维表示是男生还是女生走过。
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 7;
char a[maxn][maxn];
int n, m;
struct Point
{
int x, y;
int flag; // 如果是0，表示是erriyue ，否则是他的女朋友
};
bool vis[maxn][maxn][2]; // 代表是否占领 最后一个维度表示是erriyue标记，还是女朋友标记的
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
vector<Point> op; // 鬼魂存储的位置信息
int sum_t = 0; // 总时间
int dis(Point A, Point B) // 曼哈顿距离计算
{
return abs(A.x - B.x) + abs(A.y - B.y);
}
bool check1(int x, int y, int k) // 检查范围是否合法
{
if (a[x][y] != 'X' && x >= 1 && x <= n && y >= 1 && y <= m && vis[x][y][k] == 0)
{
return true;
}
return false;
}
bool check2(Point A) // 检查是否会被追上
{
for (int i = 0; i < 2; i++)
{
if (dis(A, op[i]) <= 2 * sum_t) // 说明被追上了
{
return false;
}
}
return true;
}
queue<Point> Q1; // 男生
queue<Point> Q2; // 女生
int bfs()
{
// 相当于是两个点的同时出发，多源点出发
while (!Q1.empty() && !Q2.empty())
{
sum_t++; // 时间+1
int total = 3; // 代表总共的循环次数
while (total--)
{
int len = Q1.size();
while (len--) // 每一点都需要跑三次
{
Point u = Q1.front();
Q1.pop(); // 直接删除
if (!check2(Point{u.x, u.y}))
{
continue;
}
for (int i = 0; i < 4; i++) // 四个方向
{
int xx = u.x + dx[i];
int yy = u.y + dy[i];
if (check1(xx, yy, u.flag) && check2(Point{xx, yy}))
{
vis[xx][yy][u.flag] = 1;
if (vis[xx][yy][!u.flag] == 1)
{
return sum_t; // 说明找到答案了
}
Q1.push(Point{xx, yy, u.flag});
}
}
}
}
total = 1; // 代表总共的循环次数
while (total--)
{
int len = Q2.size();
while (len--) // 每一点都需要跑一次
{
Point u = Q2.front();
Q2.pop(); // 直接删除
if (!check2(Point{u.x, u.y}))
{
continue;
}
for (int i = 0; i < 4; i++) // 四个方向
{
int xx = u.x + dx[i];
int yy = u.y + dy[i];
if (check1(xx, yy, u.flag) && check2(Point{xx, yy}))
{
vis[xx][yy][u.flag] = 1;
if (vis[xx][yy][!u.flag] == 1)
{
return sum_t; // 说明找到答案了
}
Q2.push(Point{xx, yy, u.flag});
}
}
}
}
}
return -1;
}
void init() // 清空
{
memset(vis, 0, sizeof(vis));
sum_t = 0; // 初始化操作
while (!Q1.empty())
{
Q1.pop();
}
while (!Q2.empty())
{
Q2.pop();
}
op.clear();
return;
}
int main()
{
int t;
cin >> t;
while (t--)
{
init();
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
if (a[i][j] == 'M') // 记录男生起点
{
Q1.push(Point{i, j, 0});
vis[i][j][0] = 1;
}
if (a[i][j] == 'G') // 记录女生起点
{
Q2.push(Point{i, j, 1});
vis[i][j][1] = 1;
}
if (a[i][j] == 'Z') // 鬼魂位置
{
op.push_back(Point{i, j});
}
}
}
cout << bfs() << endl;
}
return 0;
}