// Mecho
// https://oj.uz/problem/view/IOI09_mecho
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <array>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <list>
#include <float.h>
#include <climits>
#include <cmath>
using namespace std;
void quit() {
cout.flush();
exit(0);
}
int n, s;
pair<int, int> st, dest;
bool tree[800][800]; //contains trees and grass. bee hives are also trees
bool tmp[800][800];
bool mecho_done[800][800];
deque<pair<int, int>> hives, mecho, tmp1, tmp2, new_hives, new_mecho;
pair<int, int> gto[4] = {{0,1}, {0,-1}, {-1,0}, {1,0}};
bool in_grid(int a, int b){
return a >= 0 && a < n && b >= 0 && b < n;
}
bool bee_can_go(int a, int b){
return in_grid(a,b) && !(a == dest.first && b == dest.second) && !tree[a][b];
}
bool mecho_can_go(int a, int b){
return in_grid(a,b) && !mecho_done[a][b] && !tree[a][b];
}
void bee_expand(){
new_hives.clear();
while(!hives.empty()){
pair<int, int> curr = hives.front();
int cx = curr.first, cy = curr.second;
hives.pop_front();
for(const auto &to : gto){
int nx = to.first +cx, ny = to.second+cy;
if(bee_can_go(nx, ny)){
new_hives.emplace_back(nx, ny);
tree[nx][ny]=1;
}
}
}
hives=new_hives;
}
bool finished;
bool mecho_expand(){
//if can't expand anymore return false
for(int i = 0; i < s; i++){
new_mecho.clear();
while(!mecho.empty()){
pair<int, int> curr = mecho.front();
int cx = curr.first, cy = curr.second;
mecho.pop_front();
if(tree[cx][cy]){
continue;
}
for(const auto &to : gto){
int nx = to.first +cx, ny = to.second+cy;
if(mecho_can_go(nx, ny)){
new_mecho.emplace_back(nx, ny);
mecho_done[nx][ny]=1;
}
if(nx == dest.first && ny == dest.second){
//can get to dest
finished=true;
return false;
}
}
}
mecho=new_mecho;
}
return mecho.size()>0;
}
bool good(int wait_time){
tmp1 = hives;
tmp2 = mecho;
for(int i = 0; i < 800; i++){
for(int j = 0; j < 800; j++){
mecho_done[i][j]=0;
tmp[i][j]=tree[i][j];
}
}
mecho_done[st.first][st.second]=1;
finished=false;
//propogate until can't
for(int i = 0; i < wait_time; i++){
bee_expand();
}
while(mecho_expand()){
bee_expand();
/*
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cerr <<tree[i][j] << " ";
}
cerr << "\n";
}
*/
}
//reset variables
for(int i = 0; i < 800; i++){
for(int j = 0; j < 800; j++){
tree[i][j]=tmp[i][j];
}
}
hives=tmp1;
mecho=tmp2;
return finished;
}
int main(void){
//freopen("qwer.in", "r", stdin);
//freopen("qwer.out", "w", stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> s;
for(int i = 0; i < n; i++){
string s; cin >> s;
for(int j = 0; j < n; j++){
if(s[j]=='T'){
tree[i][j]=1;
}
else if(s[j]=='M'){
st={i,j};
mecho.emplace_back(i,j);
}
else if(s[j]=='D'){
dest = {i,j};
}
else if(s[j] == 'H'){
hives.emplace_back(i,j);
tree[i][j]=1;
}
}
}
if(!good(0)){
cout << "-1\n";
quit();
}
int s = 0, e = 1e6;
while(s != e){
int md = (s+e+1)/2;
if(good(md)){
s=md;
}
else{
e=md-1;
}
}
cout << s << "\n";
quit();
}
