#include <bits/stdc++.h> using namespace std; #define ll long long #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--) #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++) #define MAX 805 const int INF = 1e9; char forest[MAX][MAX]; int bear[MAX][MAX]; int bees[MAX][MAX]; bool vis[MAX][MAX]; int n, s; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int mecho1, mecho2, home1, home2; bool ok(int x, int y) { return (x >= 1 && y >= 1 && x <= n && y <= n && forest[x][y] != 'T' && forest[x][y] != 'H'); } bool reached(int x, int y) { return (x / s < y); } void solve() { cin >> n >> s; FOR(i, 1, n) FOR(j, 1, n) { cin >> forest[i][j]; if (forest[i][j] == 'M') { mecho1 = i; mecho2 = j; } if (forest[i][j] == 'D') { home1 = i; home2 = j; } } queue<pair<int,int>> q; FOR(i, 1, n) FOR(j, 1, n) { if (forest[i][j] == 'H') { vis[i][j] = true; q.push({i, j}); } else bees[i][j] = INF; } while (!q.empty()) { pair<int,int> cur = q.front(); q.pop(); int x = cur.first, y = cur.second; FOR(d, 0, 3) { int nx = x + dx[d]; int ny = y + dy[d]; if (ok(nx, ny) && !vis[nx][ny] && forest[nx][ny] != 'D') { bees[nx][ny] = bees[x][y] + 1; vis[nx][ny] = true; q.push({nx, ny}); } } } int low = 0, high = n * n + 2027, answer = 0; while (low <= high) { int mid = (low + high) / 2; FOR(i, 1, n) FOR(j, 1, n) { vis[i][j] = false; if (i == mecho1 && j == mecho2) bear[i][j] = 0; else bear[i][j] = INF; } queue<pair<int,int>> q; q.push({mecho1, mecho2}); vis[mecho1][mecho2] = true; if (mid >= bees[mecho1][mecho2]) q.pop(); while (!q.empty()) { pair<int,int> cur = q.front(); q.pop(); int x = cur.first, y = cur.second; FOR(d, 0, 3) { int nx = x + dx[d]; int ny = y + dy[d]; if (ok(nx, ny) && reached(bear[x][y] + 1, bees[nx][ny] - mid) && !vis[nx][ny]) { bear[nx][ny] = bear[x][y] + 1; vis[nx][ny] = true; q.push({nx, ny}); } } } bool reach = false; FOR(d, 0, 3) { int nx = home1 + dx[d]; int ny = home2 + dy[d]; if (ok(nx, ny) && reached(bear[nx][ny], bees[nx][ny] - mid) && vis[nx][ny]) { reach = true; break; } } if (reach) { answer = mid; low = mid + 1; } else high = mid - 1; } cout << (answer == 0 ? -1 : answer) << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); solve(); }