#include <bits//stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; #define ll long long #define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1)) #define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1)) #define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1)) #define pll pair<ll, ll> #define INF 1000000000000000 #define MOD1 1000000007 #define MOD2 998244353 #define MOD3 1000000009 int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll n, m; cin >> n >> m; char a[n][n]; pll x, y; ll dist[n][n]; bool vis[n][n]; queue<pll> q; iloop(0, n) jloop(0, n) { dist[i][j] = INF; vis[i][j] = 0; cin >> a[i][j]; if (a[i][j] == 'M') x = {i, j}; if (a[i][j] == 'D') y = {i, j}, vis[i][j] = 1; if (a[i][j] == 'T') vis[i][j] = 1; if (a[i][j] == 'H') { q.push({i, j}); dist[i][j] = 0; vis[i][j] = 1; } } while (q.size()) { pll nd = q.front(); q.pop(); ll dst = dist[nd.first][nd.second] + 1; if (nd.first != 0 && !vis[nd.first-1][nd.second]) { q.push({nd.first-1, nd.second}); dist[nd.first-1][nd.second] = dst; vis[nd.first-1][nd.second] = 1; } if (nd.first != n-1 && !vis[nd.first+1][nd.second]) { q.push({nd.first+1, nd.second}); dist[nd.first+1][nd.second] = dst; vis[nd.first+1][nd.second] = 1; } if (nd.second != 0 && !vis[nd.first][nd.second-1]) { q.push({nd.first, nd.second-1}); dist[nd.first][nd.second-1] = dst; vis[nd.first][nd.second-1] = 1; } if (nd.second != n-1 && !vis[nd.first][nd.second+1]) { q.push({nd.first, nd.second+1}); dist[nd.first][nd.second+1] = dst; vis[nd.first][nd.second+1] = 1; } } ll lb = -1, ub = n*n, mid; while (lb < ub) { mid = (lb + ub + 1) >> 1; bool v[n][n]; ll dd[n][n]; memset(v, 0, sizeof(v)); iloop(0, n) jloop(0, n) { dd[i][j] = INF; if (a[i][j] == 'T' || a[i][j] == 'M') v[i][j] = 1; } dd[x.first][x.second] = mid * m; q.push({x.first, x.second}); while (q.size()) { pll nd = q.front(); q.pop(); ll dst = dd[nd.first][nd.second] + 1; if (nd.first != 0 && dst < dist[nd.first-1][nd.second] * m && !v[nd.first-1][nd.second]) { q.push({nd.first-1, nd.second}); dd[nd.first-1][nd.second] = dst; v[nd.first-1][nd.second] = 1; } if (nd.first != n-1 && dst < dist[nd.first+1][nd.second] * m && !v[nd.first+1][nd.second]) { q.push({nd.first+1, nd.second}); dd[nd.first+1][nd.second] = dst; v[nd.first+1][nd.second] = 1; } if (nd.second != 0 && dst < dist[nd.first][nd.second-1] * m && !v[nd.first][nd.second-1]) { q.push({nd.first, nd.second-1}); dd[nd.first][nd.second-1] = dst; v[nd.first][nd.second-1] = 1; } if (nd.second != n-1 && dst < dist[nd.first][nd.second+1] * m && !v[nd.first][nd.second+1]) { q.push({nd.first, nd.second+1}); dd[nd.first][nd.second+1] = dst; v[nd.first][nd.second+1] = 1; } } if (v[y.first][y.second] == 1 && dd[x.first][x.second] < dist[x.first][x.second]) lb = mid; else ub = mid - 1; } cout << lb; }