#include <iostream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
struct Position {
int x, y, time;
};
int N, S;
vector<string> forest;
vector<vector<int>> bee_time, mecho_time;
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool is_valid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N && forest[x][y] != 'T';
}
void bfs_bees() {
queue<Position> q;
bee_time.assign(N, vector<int>(N, INT_MAX));
// Start BFS from all hives
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (forest[i][j] == 'H') {
q.push({i, j, 0});
bee_time[i][j] = 0;
}
}
}
while (!q.empty()) {
Position current = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = current.x + directions[i][0], ny = current.y + directions[i][1];
if (is_valid(nx, ny) && forest[nx][ny] == 'G' && bee_time[nx][ny] == INT_MAX) {
bee_time[nx][ny] = current.time + 1;
q.push({nx, ny, current.time + 1});
}
}
}
}
void bfs_mecho(int start_x, int start_y) {
queue<Position> q;
mecho_time.assign(N, vector<int>(N, INT_MAX));
q.push({start_x, start_y, 0});
mecho_time[start_x][start_y] = 0;
while (!q.empty()) {
Position current = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = current.x + directions[i][0], ny = current.y + directions[i][1];
if (is_valid(nx, ny) && forest[nx][ny] == 'G' && mecho_time[nx][ny] == INT_MAX) {
mecho_time[nx][ny] = current.time + 1;
q.push({nx, ny, current.time + 1});
}
}
}
}
int main() {
cin >> N >> S;
forest.resize(N);
Position mecho_start, mecho_home;
for (int i = 0; i < N; i++) {
cin >> forest[i];
for (int j = 0; j < N; j++) {
if (forest[i][j] == 'M') {
mecho_start = {i, j, 0};
}
if (forest[i][j] == 'D') {
mecho_home = {i, j, 0};
}
}
}
bfs_bees();
bfs_mecho(mecho_start.x, mecho_start.y);
int low = 0, high = INT_MAX;
int best_time = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
bool can_reach_home = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (forest[i][j] == 'G' && mecho_time[i][j] <= mid && bee_time[i][j] > mid) {
can_reach_home = true;
}
}
}
if (can_reach_home) {
best_time = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << best_time << endl;
return 0;
}
