#include <bits/stdc++.h>
using namespace std;
int main() {
int n, s;
cin >> n >> s;
vector<string> vs(n);
for (auto &a : vs)
cin >> a;
vector<pair<int, int>> hs2, ms2;
int xd, yd;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (vs[i][j] == 'M')
ms2.emplace_back(i, j);
else if (vs[i][j] == 'D')
xd = i, yd = j;
else if (vs[i][j] == 'H')
hs2.emplace_back(i, j);
vector<vector<int>> status; // G = 0, M = 1, H = 2
vector<pair<int, int>> hs, ms;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
auto mwalk = [&]() {
vector<pair<int, int>> newms;
for (auto [x, y] : ms) {
if (status[x][y] != 0)
continue;
status[x][y] = 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && status[nx][ny] == 0 &&
(vs[nx][ny] == 'G' || vs[nx][ny] == 'D'))
newms.emplace_back(nx, ny);
}
}
ms.swap(newms);
};
auto hwalk = [&]() {
vector<pair<int, int>> newhs;
for (auto [x, y] : hs) {
if (status[x][y] == 2)
continue;
status[x][y] = 2;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && status[nx][ny] != 2 &&
(vs[nx][ny] == 'G' || vs[nx][ny] == 'M'))
newhs.emplace_back(nx, ny);
}
}
hs.swap(newhs);
};
int l = 0, r = 1e9;
while (l < r) {
int mid = (l + r + 1) / 2;
// cout << mid << "\n";
status = vector<vector<int>>(n, vector<int>(n, 0)); // 0 = G, 1 = M, 2 = H
hs = hs2, ms = ms2;
mwalk(), hwalk();
for (int i = 0; i < mid && !hs.empty(); i++)
hwalk();
// for (auto a : status) {
// for (auto b : a)
// cout << b << " ";
// cout << "\n";
// }
while (!ms.empty()) {
for (int i = 0; i < s && !ms.empty(); i++)
mwalk();
hwalk();
}
// for (auto a : status) {
// for (auto b : a)
// cout << b << " ";
// cout << "\n";
// }
if (status[xd][yd] == 0) {
r = mid - 1;
} else {
l = mid;
}
}
status = vector<vector<int>>(n, vector<int>(n, 0)); // 0 = G, 1 = M, 2 = H
hs = hs2, ms = ms2;
mwalk(), hwalk();
for (int i = 0; i < l && !hs.empty(); i++)
hwalk();
while (!ms.empty()) {
for (int i = 0; i < s && !ms.empty(); i++)
mwalk();
hwalk();
}
if (status[xd][yd] == 0) {
cout << "-1\n";
} else {
cout << l << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |