#include <bits/stdc++.h> using namespace std; #define el "\n" #define pii pair<int, int> #define pll pair<ll, ll> #define fi first #define se second #define FOR(i, l, r) for (int i = (l); i <= (r); i++) #define FOD(i, l, r) for (int i = (l); i >= (r); i--) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((int)(x).size()) #define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); using db = long double; using ll = long long; using ull = unsigned long long; using vi = vector<int>; using vll = vector<ll>; using vpii = vector<pii>; using vpll = vector<pll>; using vvi = vector<vi>; using vvll = vector<vll>; using vbool = vector<bool>; using vvbool = vector<vbool>; template<class T> bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); } template<class T> bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); } // #define DEBUG #ifdef DEBUG #include "D:\cpp\debug.cpp" #else #define debug(...) #define debug_arr(...) #endif mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); constexpr int N = 805; constexpr int INF = 1E9 + 7; constexpr ll INFLL = 1E18; constexpr int MOD = 1E9 + 7; // 998244353 constexpr double EPS = 1E-10; char grid[N][N]; int bees_time[N][N], mecho_time[N][N]; int sx, sy, tx, ty; int n, s; const int directions[4][2] = {{-1, 0}, {+1, 0}, {0, -1}, {0, +1}}; bool valid_cell(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= n && grid[x][y] != 'T'; } bool can_mecho_reach(int mecho_time, int bees_time) { return mecho_time / s < bees_time; } bool check(int delay) { memset(mecho_time, -1, sizeof mecho_time); queue<pii> q; q.emplace(sx, sy); mecho_time[sx][sy] = 0; if (bees_time[sx][sy] <= delay) q.pop(); while (!q.empty()) { auto [x, y] = q.front(); q.pop(); if (x == tx && y == ty) return true; for (auto &[dx, dy] : directions) { int nx = x + dx, ny = y + dy; if (!valid_cell(nx, ny)) continue; if (mecho_time[nx][ny] == -1 && can_mecho_reach(mecho_time[x][y] + 1, bees_time[nx][ny] - delay)) { mecho_time[nx][ny] = mecho_time[x][y] + 1; q.emplace(nx, ny); } } } return false; } void solve() { cin >> n >> s; memset(bees_time, -1, sizeof bees_time); queue<pii> q; FOR(i, 1, n) { FOR(j, 1, n) { cin >> grid[i][j]; if (grid[i][j] == 'M') { sx = i; sy = j; } else if (grid[i][j] == 'D') { tx = i; ty = j; } else if (grid[i][j] == 'H') { q.emplace(i, j); bees_time[i][j] = 0; } } } bees_time[tx][ty] = INF; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (auto const &[dx, dy] : directions) { int nx = x + dx, ny = y + dy; if (!valid_cell(nx, ny)) continue; if (bees_time[nx][ny] == -1) { bees_time[nx][ny] = bees_time[x][y] + 1; q.emplace(nx, ny); } } } int l = 0, r = n * n, res = 0; while (l <= r) { int m = (l + r) / 2; if (check(m)) { res = m; l = m + 1; } else { r = m - 1; } } cout << (!check(res) ? -1 : res) << el; } int main() { fast_io #define LOCAL #ifndef LOCAL #define PROBLEM "" freopen(PROBLEM ".INP", "r", stdin); freopen(PROBLEM ".OUT", "w", stdout); #endif int t = 1; // cin >> t; while (t--) solve(); }