#include <bits/stdc++.h>
using namespace std ;
const int N = 1001 ;
int dx[]{0 , 0 , 1 , -1} ;
int dy[]{1 , -1 , 0 , 0} ;
int n , s ;
pair <int , int> Honey , Home ;
char a[N][N] ;
bool is[N][N] ;
bool inside(int x , int y) {
return (x >= 0 && y >= 0 && x < n && y < n && a[x][y] != 'T') ;
}
int ok(int time) {
fill_n(&is[0][0] , N * N , false ) ;
int mn2[n][n] ;
fill_n(&mn2[0][0] , n*n , 1e9) ;
queue<pair <int , int>> q2 ;
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < n ; j++) {
if(a[i][j] == 'H') {
q2.push({i, j}) ;
is[i][j] = true ;
mn2[i][j] = 0 ;
}
}
}
while(q2.size()) {
pair <int , int> t = q2.front() ;
q2.pop() ;
for(int i = 0 ; i < 4 ; i++) {
int x = t.first + dx[i] ;
int y = t.second + dy[i] ;
if(inside(x , y) && mn2[t.first][t.second] + 1 < mn2[x][y] && mn2[t.first][t.second] + 1 < time) {
is[x][y] = true ;
mn2[x][y] = mn2[t.first][t.second] + 1 ;
q2.push({x, y}) ;
}
}
}
// for(int i = 0 ; i < n ; i++) {
// for(int j = 0 ; j < n ; j++) {
// cout << is[i][j] << " " ;
// }
// cout << endl ;
// }
int mn[n][n] ;
fill_n(&mn[0][0] , n * n , 1e9 ) ;
queue <pair <int , int>> q ;
mn[Honey.first][Honey.second] = 0 ;
if(!is[Honey.first][Honey.second])
q.push(Honey) ;
while(!q.empty()) {
pair <int , int> t = q.front() ;
q.pop() ;
for(int i = 0 ; i < 4 ; i++) {
int x = t.first + dx[i] ;
int y = t.second + dy[i] ;
if(is[x][y] == false && inside(x , y) && mn[t.first][t.second] + 1 < mn[x][y]) {
mn[x][y] = mn[t.first][t.second] + 1 ;
q.push({x , y}) ;
}
}
}
// for(int i = 0 ; i < n ; i++) {
// for(int j = 0 ; j < n ; j++) {
// cout << mn[i][j] << " " ;
// }
// cout << endl ;
// }
if(mn[Home.first][Home.second] == 1e9)
return -1 ;
int req = (mn[Home.first][Home.second] / time) + (mn[Home.first][Home.second] % time != 0) ;
return time - req ;
}
int main() {
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cout.tie(0) ;
cin >> n >> s ;
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < n ; j++) {
cin >> a[i][j] ;
if(a[i][j] == 'M')
Honey = {i , j} ;
if(a[i][j] == 'D')
Home = {i , j} ;
}
}
int l = 0 , r = 1e9 ;
while(l + 1 < r) {
int m = l + (r - l) / 2 ;
if(ok(m) >= 0)
l = m ;
else
r = m ;
}
cout << ok(l) << endl ;
}
