// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
struct pos{
ll x,y;
};
vector <ll> lx = {0,0,1,-1};
vector <ll> ly = {1,-1,0,0};
void solve(){
ll n,s;
cin >> n >> s;
vector <vector <char>> l1(n, vector<char>(n));
pos startpos, endpos;
for (int i = 0; i < n; i++){
for (int j= 0; j < n; j++){
char a;
cin >> a;
l1[i][j] = a;
if (a == 'M'){
startpos = {i,j};
}
if (a == 'D'){
endpos = {i,j};
}
}
}
auto check1 = [&](ll x, ll y){
if (x >= 0 && x < n && y >= 0 && y < n){
return true;
}
return false;
};
auto bfs = [&](ll val) -> bool{
vector <vector <bool>> visited_bear(n, vector<bool>(n, false)), visited_bee(n, vector<bool>(n, false));
queue <pos> q1,q2;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (l1[i][j] == 'H'){
q1.push({i,j});
}
}
}
for (int i = 0; i < val + 1; i++){
ll idk = q1.size();
for (int j = 0; j < idk; j++){
auto cur = q1.front();
q1.pop();
if (visited_bee[cur.x][cur.y]){
continue;
}
visited_bee[cur.x][cur.y] = true;
for (int z = 0; z < 4; z++){
pos new_pos = {cur.x + lx[z], cur.y + ly[z]};
if (check1(new_pos.x, new_pos.y) && l1[new_pos.x][new_pos.y] != 'D' && l1[new_pos.x][new_pos.y] != 'T'){
q1.push(new_pos);
}
}
}
}
q2.push(startpos);
while (q1.size() >= 1 || q2.size() >= 1){
for (int i = 0; i < s; i++){
ll idk = q2.size();
for (int j = 0; j < idk; j++){
auto cur = q2.front();
q2.pop();
if (cur.x == endpos.x && cur.y == endpos.y) return true;
if (visited_bee[cur.x][cur.y] || visited_bear[cur.x][cur.y]){
continue;
}
visited_bear[cur.x][cur.y] = true;
for (int z = 0; z < 4; z++){
pos newpos = {cur.x + lx[z], cur.y + ly[z]};
if (check1(newpos.x, newpos.y) && l1[newpos.x][newpos.y] != 'T'){
q2.push(newpos);
}
}
}
}
ll idk = q1.size();
for (int j = 0; j < idk; j++){
auto cur = q1.front();
q1.pop();
if (visited_bee[cur.x][cur.y]){
continue;
}
visited_bee[cur.x][cur.y] = true;
for (int z = 0; z < 4; z++){
pos new_pos = {cur.x + lx[z], cur.y + ly[z]};
if (check1(new_pos.x, new_pos.y) && l1[new_pos.x][new_pos.y] != 'D' && l1[new_pos.x][new_pos.y] != 'T'){
q1.push(new_pos);
}
}
}
}
return visited_bear[endpos.x][endpos.y];
};
ll l = 0; ll r = 1e6;
while (l != r){
ll mid = (l+r+1)/2;
if (bfs(mid)){
l = mid;
}
else{
r = mid - 1;
}
}
cout << l << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
