考虑双向广搜。
我们需要记录男孩和女孩的当前位置，并且每次都进行扩展。
记录一个数组 (st[i][j]) 。
- 如果 (st[i][j]=0) ，说明 ((i,j)) 还没有被男孩和女孩经过；
- 如果 (st[i][j]=1) ，说明 ((i,j)) 被男孩经过了；
- 如果 (st[i][j]=2) ，说明 ((i,j)) 被女孩经过了。
如果当前扩展的是男孩，且当前的位置是 ((x,y)) ，那么当 (st[x][y]=2) 时直接返回当前扩展的层数即可；
如果当前扩展的是女孩，那么当 (st[x][y]=1) 时直接返回就可以了。
题目中有一句话：
在第 (k) 秒后所有与鬼的曼哈顿距离不超过 (2k) 的位置都会被鬼占领。
我们根据这句话的提示判断该点是否要扩展即可。
其实双队列来实现双向广搜还是比较易懂的。
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d
", __FUNCTION__, __LINE__)
#define itn int
#define gI gi
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int maxn = 803;
int t, n, m;
char s[maxn][maxn];
int st[maxn][maxn];
pair <int, int> boy, girl, ghost[5];
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
inline bool check(int x, int y, int step)
{
if (x <= 0 || x > n || y <= 0 || y > n || s[x][y] == 'X') return false; //出界了或者走到了墙
for (int i = 1; i <= 2; i+=1)
if (abs(x - ghost[i].first) + abs(y - ghost[i].second) <= step * 2) return false; //判断与鬼的曼哈顿距离
return true;
}
inline int bfs()
{
memset(st, 0, sizeof(st)); //记得数组初始化
queue <pair <int, int> > qb, qg;
int tot = 0;
for (int i = 1; i <= n; i+=1)
{
for (int j = 1; j <= m; j+=1)
{
if (s[i][j] == 'M') boy = (make_pair)(i, j);
else if (s[i][j] == 'G') girl = (make_pair)(i, j);
else if (s[i][j] == 'Z') ghost[++tot] = (make_pair)(i, j);
//记录男孩、女孩和鬼的位置
}
}
qb.push(boy); qg.push(girl);
int step = 0; //扩展的层数
while (qb.size() || qg.size()) //如果还可以扩展
{
++step;
for (int i = 1; i <= 3; i+=1) //男孩扩展 3 步
{
for (int j = 1, len = qb.size(); j <= len; j+=1) //要对队列中的每一个元素进行扩展
{
pair <int, int> p = qb.front(); qb.pop();
int x = p.first, y = p.second;
if (!check(x, y, step)) continue;
for (int k = 0; k < 4; k+=1)
{
int xx = x + dx[k], yy = y + dy[k];
if (!check(xx, yy, step)) continue;
if (st[xx][yy] == 2) return step;
if (!st[xx][yy])
st[xx][yy] = 1, qb.push((make_pair)(xx, yy));
}
}
}
for (int i = 1; i <= 1; i+=1) //女孩只要扩展一步
{
for (int j = 1, len = qg.size(); j <= len; j+=1)
{
pair <int, int> p = qg.front(); qg.pop();
int x = p.first, y = p.second;
if (!check(x, y, step)) continue;
for (int k = 0; k < 4; k+=1)
{
int xx = x + dx[k], yy = y + dy[k];
if (!check(xx, yy, step)) continue;
if (st[xx][yy] == 1) return step;
if (!st[xx][yy])
st[xx][yy] = 2, qg.push((make_pair)(xx, yy));
}
}
}
}
return -1; //无解
}
int main()
{
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
t = gi();
while (t--)
{
n = gi(), m = gi();
for (int i = 1; i <= n; i+=1) scanf("%s", s[i] + 1);
printf("%d
", bfs());
}
return 0;
}