#include <bits/stdc++.h> using namespace std; vector<string> graph; int n, s; bool reached(int bear_time, int bee_time) { return bear_time / s < bee_time; } bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n && (graph[x][y] == 'G' || graph[x][y] == 'M'); } int main() { pair<int, int> bear, home; vector<pair<int, int>> hives; cin >> n >> s; graph.resize(n); for (int i = 0; i < n; i++) { cin >> graph[i]; for (int j = 0; j < n; j++) { if (graph[i][j] == 'M') { bear = {i, j}; } else if (graph[i][j] == 'H') { hives.push_back({ i, j }); } else if (graph[i][j] == 'D') { home = { i, j }; } } } int l = 0, r = n * n; // n * n = 800 * 800 - so doable i think? N^2logN int dx[] = {-1, 0, 1, 0}; int dy[] = {0, -1, 0, 1}; while (l < r) { int eating_time = (l + r) / 2; queue<pair<int, int>> q; vector<vector<int>> bee_time(n, vector<int>(n)); vector<vector<int>> bear_time(n, vector<int>(n)); vector<vector<bool>> bear_visited(n, vector<bool>(n)); vector<vector<bool>> bee_visited(n, vector<bool>(n)); for (auto [x, y] : hives) { q.push({ x, y }); bee_visited[x][y] = true; } while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (valid(nx, ny) && !bee_visited[nx][ny]) { q.push({ nx, ny}); bee_visited[nx][ny] = true; bee_time[nx][ny] = bee_time[x][y] + 1; } } } q.push({ bear.first, bear.second }); bear_visited[bear.first][bear.second] = true; if (bee_time[bear.first][bear.second] <= eating_time) { q.pop(); } while (!q.empty()) { int x = q.front().first, y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (valid(nx, ny) && !bear_visited[nx][ny] && reached(bear_time[x][y] + 1, bee_time[nx][ny] - eating_time)) { bear_time[nx][ny] = bear_time[x][y] + 1; q.push({ nx, ny}); bear_visited[nx][ny] = true; } } } bool reachable = false; for (int i = 0; i < 4; i++) { int x = dx[i] + home.first, y = dy[i] + home.second; if (valid(x, y) && bear_visited[x][y] && reached(bear_time[x][y], bee_time[x][y] - eating_time)) { reachable = true; } } if (reachable) { l = eating_time + 1; } else { r = eating_time - 1; } } cout << l - 1 << endl; }