一、内容
给定一张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
二、思路
已知起点(男孩)，终点（女孩）进行双向bfs。由于题目给出男孩每秒钟可以走3步，所以每次循环将队列里面前一步的状态循环完，循环3次等于走了3步。检查与鬼的距离，预先判断某个点是否会被鬼给波及。vis数组记录走过该点的状态， 0表示未走过，1表示男孩走过，2表示女孩走过。
三、代码
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <iostream>
using namespace std
;
const int N
= 805;
int t
, n
, m
, vis
[N
][N
], zx1
, zy1
, zx2
, zy2
, mx
, my
, gx
, gy
, step
;
char G
[N
][N
];
int dx
[4] = {0, 1, 0, -1};
int dy
[4] = {1, 0, -1, 0};
struct node
{
int x
, y
;
node(int xx
, int yy
) {
x
= xx
; y
= yy
; ;
}
};
bool ok(int x
, int y
) {
if (x
< 0 || y
< 0 || x
>= n
|| y
>= m
|| G
[x
][y
] == 'X') return false;
if (abs(x
- zx1
) + abs(y
- zy1
) <= 2 * step
) return false;
if (abs(x
- zx2
) + abs(y
- zy2
) <= 2 * step
) return false;
return true;
}
int bfs() {
memset(vis
, 0, sizeof(vis
));
vis
[mx
][my
] = 1;
vis
[gx
][gy
] = 2;
step
= 0;
queue
<node
> qm
, qg
;
qm
.push(node(mx
, my
));
qg
.push(node(gx
, gy
));
while (!qm
.empty() && !qg
.empty()) {
step
++;
for (int k
= 0; k
< 3; k
++) {
for (int i
= 0, len
= qm
.size(); i
< len
; i
++) {
node t
= qm
.front();
qm
.pop();
if (!ok(t
.x
, t
.y
)) continue;
for (int j
= 0; j
< 4; j
++) {
int fx
= t
.x
+ dx
[j
];
int fy
= t
.y
+ dy
[j
];
if (!ok(fx
, fy
) || vis
[fx
][fy
] == vis
[t
.x
][t
.y
]) continue;
if (vis
[fx
][fy
] + vis
[t
.x
][t
.y
] == 3) {
return step
;
}
vis
[fx
][fy
] = vis
[t
.x
][t
.y
];
qm
.push(node(fx
, fy
));
}
}
}
for (int i
= 0, len
= qg
.size(); i
< len
; i
++) {
node t
= qg
.front();
qg
.pop();
if (!ok(t
.x
, t
.y
)) continue;
for (int j
= 0; j
< 4; j
++) {
int fx
= t
.x
+ dx
[j
];
int fy
= t
.y
+ dy
[j
];
if (!ok(fx
, fy
) || vis
[fx
][fy
] == vis
[t
.x
][t
.y
]) continue;
if (vis
[fx
][fy
] + vis
[t
.x
][t
.y
] == 3) {
return step
;
}
vis
[fx
][fy
] = vis
[t
.x
][t
.y
];
qg
.push(node(fx
, fy
));
}
}
}
return -1;
}
int main() {
scanf("%d", &t
);
while (t
--) {
scanf("%d%d", &n
, &m
);
for (int i
= 0; i
< n
; i
++) {
scanf("%s", G
[i
]);
}
int cnt
= 0;
for (int i
= 0; i
< n
; i
++) {
for (int j
= 0; j
< m
; j
++) {
if (G
[i
][j
] == 'Z') {
if (!cnt
){
zx1
= i
; zy1
= j
;
cnt
++;
} else {
zx2
= i
; zy2
= j
;
}
}
if (G
[i
][j
] == 'M') mx
= i
, my
= j
;
if (G
[i
][j
] == 'G') gx
= i
, gy
= j
;
}
}
printf("%d\n", bfs());
}
return 0;
}
