1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 8e2 + 50;
const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
char s[maxn][maxn];
bool M[maxn][maxn], G[maxn][maxn];
int r, c, ans;
struct node {
int x_, y_;
node(int x = 0, int y = 0) : x_(x), y_(y) {}
} m, g, z1, z2;
queue<node> mq, gq;
bool valid(int x, int y) {
if (x < 1 || y < 1 || x > r || y > c) return 0;
if (s[x][y] == 'X') return 0;
if (abs(x - z1.x_) + abs(y - z1.y_) <= 2 * ans) return 0;
if (abs(x - z2.x_) + abs(y - z2.y_) <= 2 * ans) return 0;
return 1;
}
void init() {
m = g = z1 = z2 = node(0, 0);
for (int i = 1; i <= r; ++i) {
for (int j = 1; j <= c; ++j) {
if (s[i][j] == 'M') {
m.x_ = i, m.y_ = j;
} else if (s[i][j] == 'G') {
g.x_ = i, g.y_ = j;
} else if (s[i][j] == 'Z') {
if (!z1.x_) {
z1.x_ = i, z1.y_ = j;
} else {
z2.x_ = i, z2.y_ = j;
}
}
}
}
ans = 0;
memset(M, 0, sizeof(M)), memset(G, 0, sizeof(G));
while (!mq.empty()) mq.pop();
while (!gq.empty()) gq.pop();
}
int bfs() {
int ms, gs;
mq.push(m), gq.push(g);
M[m.x_][m.y_] = G[g.x_][g.y_] = 1;
while (!mq.empty() || !gq.empty()) {
++ans;
for (int k = 1; k <= 3; ++k) {
ms = mq.size();
while (ms--) {
node u = mq.front();
mq.pop();
if (!valid(u.x_, u.y_)) continue;
for (int i = 0; i < 4; ++i) {
int x = u.x_ + dx[i], y = u.y_ + dy[i];
if (valid(x, y) && !M[x][y]) {
M[x][y] = 1;
mq.emplace(x, y);
}
}
}
}
gs = gq.size();
while (gs--) {
node u = gq.front();
gq.pop();
if (!valid(u.x_, u.y_)) continue;
for (int i = 0; i < 4; ++i) {
int x = u.x_ + dx[i], y = u.y_ + dy[i];
if (valid(x, y) && !G[x][y]) {
if (M[x][y]) return ans;
G[x][y] = 1;
gq.emplace(x, y);
}
}
}
}
return -1;
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> r >> c;
for (int i = 1; i <= r; ++i) scanf("%s", (s[i] + 1));
init();
cout << bfs() << endl;
}
return 0;
}
|
