#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair <int,int> const int N=805; const int INF=1e18; // ใช้ค่าที่เหมาะสม const int dy[]={-1,1,0,0}; const int dx[]={0,0,-1,1}; int n, m, d_b[N][N], d_m[N][N]; pii st, en; char c[N][N]; bool ok(int y, int x) { return (y >= 1 && y <= n && x >= 1 && x <= n); } bool check(int mid) { // 1. เช็คว่าผึ้งกินจุดเริ่มต้นไปหรือยังก่อนเริ่มเดิน if (mid * m >= d_b[st.first][st.second]) return false; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) d_m[i][j] = -1; queue<pii> q; q.push(st); d_m[st.first][st.second] = mid * m; while(!q.empty()){ auto [y, x] = q.front(); q.pop(); if (y == en.first && x == en.second) return true; for(int i=0; i<4; i++){ int yy = y + dy[i], xx = x + dx[i]; if(!ok(yy, xx) || c[yy][xx] == 'T' || c[yy][xx] == 'H' || d_m[yy][xx] != -1) continue; // 2. เงื่อนไขสำคัญ: ถ้าเป็นบ้าน (D) ไม่ต้องเช็ค d_b เพราะผึ้งเข้าไม่ได้ if (c[yy][xx] != 'D' && d_m[y][x] + 1 >= d_b[yy][xx]) continue; d_m[yy][xx] = d_m[y][x] + 1; q.push({yy, xx}); } } return false; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; queue<pii> q_b; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { d_b[i][j] = INF; cin >> c[i][j]; if(c[i][j] == 'H') { d_b[i][j] = 0; q_b.push({i, j}); } else if(c[i][j] == 'M') st = {i, j}; else if(c[i][j] == 'D') en = {i, j}; } } // ผึ้งเดินกระจายทั่วแผนที่ while(!q_b.empty()){ auto [y, x] = q_b.front(); q_b.pop(); for(int i=0; i<4; i++){ int yy = y + dy[i], xx = x + dx[i]; // ผึ้งไม่ผ่านบ้าน (D) และต้นไม้ (T) if(!ok(yy, xx) || c[yy][xx] == 'D' || c[yy][xx] == 'T' || d_b[yy][xx] != INF) continue; d_b[yy][xx] = d_b[y][x] + m; // ใช้ m เพื่อเทียบกับจำนวนก้าว (steps) q_b.push({yy, xx}); } } int l = 0, r = n * n, ans = -1; while(l <= r){ int mid = l + (r - l) / 2; if(check(mid)){ ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans; }