题目描述
给定一张N*M的地图,地图中有1个男孩,1个女孩和2个鬼。
字符“.”表示道路,字符“X”表示墙,字符“M”表示男孩的位置,字符“G”表示女孩的位置,字符“Z”表示鬼的位置。
男孩每秒可以移动3个单位距离,女孩每秒可以移动1个单位距离,男孩和女孩只能朝上下左右四个方向移动。
每个鬼占据的区域每秒可以向四周扩张2个单位距离,并且无视墙的阻挡,也就是在第k秒后所有与鬼的曼哈顿距离不超过2k的位置都会被鬼占领。
样例
输入样例:
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
算法1
(双向bfs)
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 810;
int n, m;
char g[N][N];
int st[N][N];
PII ghost[2];
bool check(int x, int y, int step){
if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == 'X') return false;
for (int i = 0; i < 2; i ++)
if (abs(x - ghost[i].first) + abs(y - ghost[i].second) <= step * 2) return false;
return true;
}
int bfs(){
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
memset(st, 0, sizeof st);
int cnt = 0;
PII boy, girl;
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
if (g[i][j] == 'M') boy = {i, j};
else if (g[i][j] == 'G') girl = {i, j};
else if (g[i][j] == 'Z') ghost[cnt ++] = {i, j};
queue<PII> qb, qg;
qb.push(boy);
qg.push(girl);
int step = 0;
while (qb.size() || qg.size()){
step ++;
for (int i = 0; i < 3; i ++)
for (int j = 0, len = qb.size(); j < len; j ++){
auto t = qb.front(); qb.pop();
int x = t.first, y = t.second;
if (!check(x, y, step)) continue;
for (int k = 0; k < 4; k ++){
int a = x + dx[k], b = y + dy[k];
if (check(a, b, step)){
if (st[a][b] == 2){
return step;
}
if (!st[a][b]){
st[a][b] = 1;
qb.push({a, b});
}
}
}
}
for (int i = 0; i < 1; i ++)
for (int j = 0, len = qg.size(); j < len; j ++){
auto t = qg.front(); qg.pop();
int x = t.first, y = t.second;
if (!check(x, y, step)) continue;
for (int k = 0; k < 4; k ++){
int a = x + dx[k], b = y + dy[k];
if (check(a, b, step)){
if (st[a][b] == 1){
return step;
}
if (!st[a][b]){
st[a][b] = 2;
qg.push({a, b});
}
}
}
}
}
return -1;
}
int main(){
int T;
scanf("%d", &T);
while (T --){
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++) scanf("%s", g[i]);
printf("%d\n", bfs());
}
return 0;
}