#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pii pair<int,int> #define all(a) a.begin(), a.end() #define el '\n' const int maxN = 805; const int base = 311; const int MOD = 1e9+7; const int INF = 1e18; const int NEG_INF = -1e18; const int MAX_DAYS = 1000; int dy[] = {-1, 1, 0, 0}; int dx[] = {0, 0, -1, 1}; int n, m, k, q, x; // string S, T; int S; int dist_mecho[maxN][maxN]; int dist_bee[maxN][maxN]; int par[maxN], deg[maxN]; bool visited[maxN]; vector<int> g[maxN]; string grid[maxN]; string dir_char = "LRUD"; pii st, ed; vector<pii> bees; bool inside(int x, int y) { return (x > 0 && x <= n && y > 0 && y <= m && grid[x][y] != 'T'); } // void bfs(pii st) { // for(int i = 1; i <= n; i++){ // for(int j = 1; j <= m; j++){ // dist[i][j] = INF; // par[i][j] = -1; // } // } // queue<tuple<int,int>> q; // q.push({st.fi, st.se}); // dist[st.fi][st.se] = 0; // while (!q.empty()) { // auto [x, y] = q.front(); // q.pop(); // if (x == ed.fi && y == ed.se) return; // for(int k = 0; k < 4; k++){ // int nx = x + dx[k], ny = y + dy[k]; // if(!inside(nx,ny)) continue; // if(dist[nx][ny] > dist[x][y] + 1){ // dist[nx][ny] = dist[x][y] + 1; // par[nx][ny] = k; // q.push({nx,ny}); // } // } // } // } bool bfs_mecho(int time_eat) { if (time_eat * 1 >= dist_bee[st.fi][st.se]) return false; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ dist_mecho[i][j] = INF; } } queue<pii> q; q.push({st.fi, st.se}); dist_mecho[st.fi][st.se] = 0; while(!q.empty()){ auto [x,y] = q.front(); q.pop(); if (x == ed.fi && y == ed.se) return true; int steps = dist_mecho[x][y] + 1; for(int k = 0; k < 4; k++){ int nx = x + dx[k], ny = y + dy[k]; // int cur_time = time_eat + (steps - 1) / S + 1; int cur_time = time_eat + steps/S; if(!inside(nx,ny) || cur_time >= dist_bee[nx][ny]) continue; if(dist_mecho[nx][ny] > dist_mecho[x][y] + 1){ dist_mecho[nx][ny] = dist_mecho[x][y] + 1; q.push({nx,ny}); } } } return false; } void bfs_bee(){ queue<pii> q; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ dist_bee[i][j] = INF; } } for(auto bee : bees){ dist_bee[bee.fi][bee.se] = 0; q.push({bee.fi, bee.se}); } while(!q.empty()){ auto [x,y] = q.front(); q.pop(); for(int k = 0; k < 4; k++){ int nx = x + dx[k], ny = y + dy[k]; if(!inside(nx,ny) || grid[nx][ny] == 'D') continue; if(dist_bee[nx][ny] > dist_bee[x][y] + 1){ dist_bee[nx][ny] = dist_bee[x][y] + 1; q.push({nx,ny}); } } } } // void Trace() { // if (dist[ed.fi][ed.se] == INF) { // cout << "NO" << el; // return; // } // cout << "YES" << el; // cout << dist[ed.fi][ed.se] << el; // string path = ""; // int cur_x = ed.fi; // int cur_y = ed.se; // while (cur_x != st.fi || cur_y != st.se) { // int k = par[cur_x][cur_y]; // path += dir_char[k]; // cur_x -= dx[k]; // cur_y -= dy[k]; // } // reverse(path.begin(), path.end()); // cout << path << el; // } void run_test() { cin >> n >> S; m = n; for(int i = 1; i <= n; i++){ string s; cin >> s; s = '_' + s; grid[i] = s; for(int j = 1; j <= m; j++){ if(grid[i][j] == 'M') st = {i, j}; if(grid[i][j] == 'D') ed = {i, j}; if(grid[i][j] == 'H'){ bees.push_back({i,j}); } } } bfs_bee(); int lo = 0; int hi = INF; while(lo <= hi){ int mid = (lo + hi) >> 1; if(bfs_mecho(mid)) lo = mid + 1; else hi = mid - 1; } cout << hi; } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); // freopen("atlarge.in", "r", stdin); // freopen("atlarge.out", "w", stdout); int test = 1; // cin >> test; while (test-- > 0) { run_test(); } }