// ============================================================================ // // || || // // || || // //*|| // Jigyasu's Template for cpp // || // // ||--------------------------Expert till July 2025-------------------------|| // // || || // // || || // // ============================================================================ // #include <bits/stdc++.h> using namespace std; #define fast_io cin.sync_with_stdio(false); cin.tie(0); cout.tie(0) // #define cerr if(false)cerr #define int long long #define ll long long #define pb push_back #define eb emplace_back #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define sz(x) (int)(x).size() #define MOD 1000000007 #define INF (int)1e16 #define endl "\n" #define sp " " // #define endl endl; cout.flush(); #define input(a, n) vi a(n); for(int i = 0; i < n; i++) cin >> a[i]; #define yes cout << "YES" << endl; return; #define no cout << "NO" << endl; return; #define vi vector<int> #define vvi vector<vector<int> > #define ai(zzz) array<int, zzz> #define pii pair<int, int> // #define f(i, a, b) for (int i = a; i < b; i++) // #define fr(i, a, b) for (int i = a; i > b; i--) //?-------------------------------------------------------------------------------------------------------------------- template <typename T> std::ostream &operator<<(std::ostream &stream, const vector<T> &vec) {for (size_t i = 0; i < vec.size(); i++) { stream << vec[i]; if (i != vec.size() - 1) stream << ' '; }; return stream; } template <typename T> std::istream &operator>>(std::istream &stream, vector<T> &vec) {for (T &x : vec) stream >> x; return stream; } template <typename T> std::istream &operator>>(std::istream &stream, array<T, 2> &arr) {stream >> arr[0] >> arr[1]; return stream; } template <typename T> std::ostream &operator<<(std::ostream &stream, const array<T, 2> &arr) {stream << '(' << arr[0] << ", " << arr[1] << ')'; return stream; } template <typename T, typename U> std::ostream &operator<<(std::ostream &stream, const pair<T, U> &pr) {stream << pr.first << ' ' << pr.second; return stream; } template <typename T, typename U> std::istream &operator>>(std::istream &stream, pair<T, U> &pr) {stream >> pr.first >> pr.second; return stream; } template <typename A, typename B> string to_string(pair<A, B> p); template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p); template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p); string to_string(const string &s) { return '"' + s + '"'; } string to_string(char c) {string s; s += c; return s; } string to_string(const char *s) { return to_string((string)s); } string to_string(bool b) { return (b ? "1" : "0"); } string to_string(vector<bool> v) {bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) {if (!first) {res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template <size_t N> string to_string(bitset<N> v) {string res = ""; for (size_t i = 0; i < N; i++) {res += static_cast<char>('0' + v[i]); } return res; } template <typename A> string to_string(A v) {bool first = true; string res = "{"; for (const auto &x : v) {if (!first) {res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; } template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cout << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cout << " " << to_string(H); debug_out(T...); } //* Debuggers #define debug(x) cout << #x << " = " << x << endl; template<typename T> void print_container(const T& container) { for (auto it = container.begin(); it != container.end(); ++it) { cout << *it; if (next(it) != container.end()) cout << " "; } cout << endl; } #define print(x) print_container(x); //?-------------------------------------------------------------------------------------------------------------------- //* Sieve of Eratosthenes for primes vector<int> sieve(int n) { vi st; // map<int, set<int> >hey_mp; vector<bool> is_prime(n + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <= n; ++i) { if (is_prime[i]) { // hey_mp[i].insert(i); for (int j = i * i; j <= n; j += i) { // if (is_prime[j]) hey_mp[i].push_back(j); is_prime[j] = false; // hey_mp[i].insert(j); } } } // return hey_mp; for (int i = 0; i <= n; i++) { if (is_prime[i]) { st.pb(i); } } return st; } //?-------------------------------------------------------------------------------------------------------------------- //* Modular Multiplication ll mod_mul(ll a, ll b) {return ((a % MOD) * (b % MOD)) % MOD;} //* Binary Exponentiation ll binpow(ll a, ll b, ll m = MOD) { ll res = 1; a %= m; while (b) { if (b & 1ll) res = res * a % m; a = mod_mul(a, a); b >>= 1ll; } return res; } //* Modular Addition ll mod_add(ll a, ll b) {return ((a % MOD) + (b % MOD)) % MOD;} //* Modular Subtraction ll mod_sub(ll a, ll b) {return ((a % MOD) - (b % MOD) + MOD) % MOD;} //* Modular Division (using Modular Inverse) ll mod_inv(ll a, ll m = MOD) {return binpow(a, m - 2, m);} // Fermat's Little Theorem ll mod_div(ll a, ll b) {return mod_mul(a, mod_inv(b));} //?-------------------------------------------------------------------------------------------------------------------- //?-------------------------------------------------------------------------------------------------------------------- int n, s, sx = -1, sy = -1, ex = -1, ey = -1; vector<vector<char>>grid; vector<vector<int>>bee_time; bool is_valid1(int i, int j, int time) { if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] == 'T' || (time / s) >= bee_time[i][j]) return false; return true; } bool bfs(int time_eaten) { queue<ai(2)>q; vector<vector<int> >dist(n, vector<int>(n, INF)); q.push({sx, sy}); dist[sx][sy] = time_eaten * s; while (!q.empty()) { auto [i, j] = q.front(); q.pop(); int t = dist[i][j] + 1; if (is_valid1(i-1, j, t) && dist[i-1][j] == INF) { q.push({i-1, j}); dist[i-1][j] = t; } if (is_valid1(i+1, j, t) && dist[i+1][j] == INF) { q.push({i+1, j}); dist[i+1][j] = t; } if (is_valid1(i, j-1, t) && dist[i][j-1] == INF) { q.push({i, j-1}); dist[i][j-1] = t; } if (is_valid1(i, j+1, t) && dist[i][j+1] == INF) { q.push({i, j+1}); dist[i][j+1] = t; } } return dist[ex][ey] != INF; } bool is_valid(int i, int j) { if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] == 'T' || grid[i][j] == 'D' || bee_time[i][j] != INF) return false; return true; } void Solve() { cin >> n >> s; grid.resize(n, vector<char>(n)); bee_time.resize(n, vector<int>(n, INF)); queue<ai(2)>q; for (int i = 0; i < n; i++) { string str; cin >> str; for (int j = 0; j < n; j++) { grid[i][j] = str[j]; if (grid[i][j] == 'M') { sx = i; sy = j; } else if (grid[i][j] == 'D') { ex = i; ey = j; } else if (grid[i][j] == 'H') { bee_time[i][j] = 0; q.push({i, j}); } } } while (!q.empty()) { auto [i, j] = q.front(); q.pop(); if (is_valid(i-1, j)) { bee_time[i-1][j] = bee_time[i][j] + 1; q.push({i-1, j}); } if (is_valid(i+1, j)) { bee_time[i+1][j] = bee_time[i][j] + 1; q.push({i+1, j}); } if (is_valid(i, j-1)) { bee_time[i][j-1] = bee_time[i][j] + 1; q.push({i, j-1}); } if (is_valid(i, j+1)) { bee_time[i][j+1] = bee_time[i][j] + 1; q.push({i, j+1}); } } int l = 0, r = 1e9, ans = -1; while (l <= r) { int mid = (l + r) / 2; if (bfs(mid)) { ans = mid; l = mid + 1; } else r = mid - 1; } cout << ans << endl; } int32_t main() { #ifndef ONLINE_JUDGE auto start = chrono::high_resolution_clock::now(); // Start timer // freopen("atlarge.in", "r", stdin); // freopen("atlarge.out", "w", stdout); #endif fast_io; int tt = 1; // cin >> tt; while (tt--) Solve(); #ifndef ONLINE_JUDGE auto end = chrono::high_resolution_clock::now(); // End timer chrono::duration<double, milli> duration = end - start; cerr << "Time: " << duration.count() << " ms" << endl; #endif }