#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <deque>
using namespace std;
#define INT long long
#define MAX_INT 2000000024
string str;
vector<vector<int>> b, bear;
vector<string> arr;
deque<pair<int, int>> q;
int n, m;
int in_map(int x, int y) {
if(x >= 0 && x < n && y >= 0 && y < n) return 1;
return 0;
}
void q_add(int x, int y, int t) {
if(!in_map(x, y)) return;
if(arr[x][y] != 'G') return;
if(b[x][y] > t) b[x][y] = t;
else return;
q_add(x+1, y, t + m);
q_add(x-1, y, t + m);
q_add(x, y+1, t + m);
q_add(x, y-1, t + m);
}
void run(int x, int y, int t) {
if(!in_map(x, y)) return;
if(arr[x][y] != 'G' && arr[x][y] != 'D') return;
//cout << x << " " << y << endl;
if(bear[x][y] > t) bear[x][y] = t;
else return;
if(bear[x][y] >= b[x][y]) return;
run(x+1, y, t+1);
run(x-1, y, t+1);
run(x, y+1, t+1);
run(x, y-1, t+1);
}
void show_b() {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(b[i][j] == MAX_INT) {
cout << "-1 ";
continue;
}
cout << b[i][j] << " ";
}
cout << endl;
}
}
void show_bear() {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(bear[i][j] == MAX_INT) {
cout << "-1 ";
continue;
}
cout << bear[i][j] << " ";
}
cout << endl;
}
}
void clear_bear() {
int i, j;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
bear[i][j] = MAX_INT;
}
}
}
int main() {
ios::sync_with_stdio(false);
//cin.tie(nullptr);
//cout.tie(nullptr);
int i, j, k, x, y, tx, ty;
cin >> n >> m;
arr.resize(n+2);
//for(auto& num : arr) num.resize(n+2);
b.resize(n+2);
for(auto& num : b) {
num.resize(n+2);
for(auto& num2 : num) {
num2 = MAX_INT;
}
}
bear.resize(n+2);
for(auto& num : bear) {
num.resize(n+2);
}
/**
for(i = 1; i <= n; i++) {
cin >> str;
for(j = 0; j < n; j++) {
if(str[j] == 'T') {
arr[i][j+1] = -1;
}
else if(str[j] == 'G') {
arr[i][j+1] = 1;
}
else if(str[j] == 'M') {
arr[i][j+1] = -MAX_INT;
}
else if(str[j] == 'D') {
arr[i][j+1] = MAX_INT;
}
else if(str[j] == 'H') {
arr[i][j+1] = 0;
}
}
}
/**/
for(i = 0; i < n; i++) {
cin >> arr[i];
for(j = 0; j < n; j++) {
if(arr[i][j] == 'H') {
b[i][j] = 0;
q_add(i+1, j, 3);
q_add(i-1, j, 3);
q_add(i, j+1, 3);
q_add(i, j-1, 3);
}
else if(arr[i][j] == 'M') {
x = i;
y = j;
}
else if(arr[i][j] == 'D') {
tx = i;
ty = j;
}
}
}
//show_b();
//return 0;
for(i = 0; ; i++) {
clear_bear();
bear[x][y] = 0;
run(x+1, y, i * m + 1);
run(x-1, y, i * m + 1);
run(x, y+1, i * m + 1);
run(x, y-1, i * m + 1);
if(bear[tx][ty] == MAX_INT) {
break;
}
}
cout << i-1;
return 0;
}
