#include <bits/stdc++.h> using namespace std; #define ll long long #define maxn 805 #define mod 1000000007 char a[maxn][maxn]; int n, s, Bee_dist[maxn][maxn], Mecho_dist[maxn][maxn]; int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}; vector<pair<int, int>> pos_hive; pair<int, int> pos_home, pos_Mecho; queue<pair<int, int>> Bee_q, Mecho_q; bool Bee_inside(int x, int y) { return (1 <= x && x <= n && 1 <= y && y <= n && a[x][y] != 'T' && a[x][y] != 'D'); } bool Mecho_inside(int x, int y) { return (1 <= x && x <= n && 1 <= y && y <= n && a[x][y] != 'T' && a[x][y] != 'H'); } bool f(int time) { memset(Bee_dist, 0x3f, sizeof Bee_dist); memset(Mecho_dist, 0x3f, sizeof Mecho_dist); for (auto [x, y] : pos_hive) { Bee_q.push({x, y}); Bee_dist[x][y] = 0; } while (Bee_q.size()) { auto [x, y] = Bee_q.front(); Bee_q.pop(); for (int dir = 0; dir < 4; dir += 1) { int newx = x + dx[dir], newy = y + dy[dir]; if (Bee_inside(newx, newy) && Bee_dist[newx][newy] > Bee_dist[x][y] + 1) { Bee_dist[newx][newy] = Bee_dist[x][y] + 1; Bee_q.push({newx, newy}); } } } Mecho_dist[pos_Mecho.first][pos_Mecho.second] = 0; Mecho_q.push({pos_Mecho.first, pos_Mecho.second}); while (Mecho_q.size()) { auto [x, y] = Mecho_q.front(); Mecho_q.pop(); if (Bee_dist[x][y] <= time) { continue; } for (int dir = 0; dir < 4; dir += 1) { int newx = x + dx[dir], newy = y + dy[dir]; if (Mecho_inside(newx, newy) && Mecho_dist[newx][newy] > Mecho_dist[x][y] + 1) { if (Mecho_dist[x][y] + 1 < s * Bee_dist[newx][newy]) { Mecho_dist[newx][newy] = Mecho_dist[x][y] + 1; Mecho_q.push({newx, newy}); } } } } for (int dir = 0; dir < 4; dir += 1) { int x = pos_home.first + dx[dir], y = pos_home.second + dy[dir]; if (Mecho_inside(x, y) && Mecho_dist[x][y] < 1e9) { return true; } } return false; } void solve() { cin >> n >> s; for (int i = 1; i <= n; i += 1) for (int j = 1; j <= n; j += 1) { cin >> a[i][j]; if (a[i][j] == 'H') { pos_hive.push_back({i, j}); } else if (a[i][j] == 'M') { pos_Mecho = {i, j}; } else if (a[i][j] == 'D') { pos_home = {i, j}; } } int l = -1, r = n * n + 1; while (r - l > 1) { int m = (l + r) / 2; if (f(m)) { l = m; } else { r = m; } } cout << l - 1; return; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int test_case = 1; // cin >> test_case; for (int i = 1; i <= test_case; i += 1) { solve(); } return 0; }