-
Notifications
You must be signed in to change notification settings - Fork 0
/
CTOI09_1-ioi2009_mecho.cpp
117 lines (97 loc) · 2.46 KB
/
CTOI09_1-ioi2009_mecho.cpp
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;
#define MAX 803
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
char original_grid[MAX][MAX];
char grid[MAX][MAX];
int bee_times[MAX][MAX];
int N, S;
int di[] = {-1, 1, 0, 0};
int dj[] = {0, 0, -1, 1};
inline bool valid_grid(int i, int j) {
return !(i < 0 || j < 0 || i >= N || j >= N);
}
inline bool bear_walkable(int i, int j) {
return valid_grid(i, j) && (grid[i][j] == 'G' || grid[i][j] == 'D');
}
inline bool valid_bee_grid(int i, int j) {
return valid_grid(i, j) && grid[i][j] == 'G';
}
inline void visit(int i, int j) { grid[i][j] = 'T'; }
void grid_cpy() {
for (int i = 0; i < N; i++)
memcpy(grid[i], original_grid[i], sizeof(char) * N);
}
void calculate_bee_times() {
grid_cpy();
queue<tiii> q;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (grid[i][j] == 'H') q.push(make_tuple(i, j, 0));
while (!q.empty()) {
auto [i, j, t] = q.front();
q.pop();
bee_times[i][j] = t;
for (int d = 0; d < 4; d++) {
int i2 = i + di[d];
int j2 = j + dj[d];
if (!valid_bee_grid(i2, j2)) continue;
visit(i2, j2);
q.push(make_tuple(i2, j2, t + S));
}
}
}
bool possible(int minutes, pii from, pii to) {
grid_cpy();
queue<tiii> q;
q.push(make_tuple(from.first, from.second, minutes));
while (!q.empty()) {
auto [i, j, t] = q.front();
q.pop();
if (to == make_pair(i, j)) return true;
visit(i, j);
if (bee_times[i][j] <= t) continue;
for (int d = 0; d < 4; d++) {
int i2 = i + di[d];
int j2 = j + dj[d];
if (!bear_walkable(i2, j2)) continue;
visit(i2, j2);
q.push(make_tuple(i2, j2, t + 1));
}
}
return false;
}
void solve() {
scanf("%d %d", &N, &S);
pii mecho, home;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
scanf(" %c", &original_grid[i][j]);
if (original_grid[i][j] == 'D')
home = make_pair(i, j);
else if (original_grid[i][j] == 'M') {
mecho = make_pair(i, j);
original_grid[i][j] = 'G';
}
}
calculate_bee_times();
int left = 0;
int right = (N * N * N);
int possible_time = -1;
while (left < right) {
int mid = (left + right) / 2;
if (possible(mid, mecho, home)) {
left = mid + 1;
possible_time = mid;
} else {
right = mid;
}
}
printf("%d\n", possible_time == -1 ? -1 : possible_time / S);
}
int main() {
int T;
scanf("%d", &T);
while (T--) solve();
}