# https://oj.uz/problem/view/IOI09_mecho
from collections import deque
n, s = map(int, input().split())
forest = []
for _ in range(n):
forest.append(input())
start = None
end = None
hives = []
for i in range(n):
for j in range(n):
if forest[i][j] == 'M':
start = (i, j)
if forest[i][j] == 'D':
end = (i, j)
if forest[i][j] == 'H':
hives.append((i, j))
def valid_square(x, y):
return 0 <= x < n and 0 <= y < n and (forest[x][y] == 'G' or forest[x][y] == 'M')
bees_time = [[0] * n for _ in range(n)]
bees_visited = [[False] * n for _ in range(n)]
Q = deque()
# move bees
for hive_x, hive_y in hives:
Q.append((hive_x, hive_y))
bees_visited[hive_x][hive_y] = True
while Q:
x, y = Q.popleft()
for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if valid_square(nx, ny) and not bees_visited[nx][ny]:
bees_time[nx][ny] = bees_time[x][y] + 1
Q.append((nx, ny))
bees_visited[nx][ny] = True
def mecho_reached(mecho_dis, bees_dis):
return mecho_dis // s < bees_dis
def ok(eating_time):
mecho_visited = [[False] * n for _ in range(n)]
mecho_time = [[0] * n for _ in range(n)]
Q = deque()
# move Mecho
Q.append(start)
mecho_visited[start[0]][start[1]] = True
if bees_time[start[0]][start[1]] <= eating_time:
Q.popleft()
while Q:
x, y = Q.popleft()
for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
'''
check if mecho reaces node[x][y] before the bees by dividing the time mecho takes to reach a node by s, since mecho walks s steps at a time.
subtract the eating time from the time taken for the bees to reach the node, because that time was used by mecho for eating
'''
if valid_square(nx, ny) and not mecho_visited[nx][ny] and mecho_reached(mecho_time[x][y] + 1, bees_time[nx][ny] - eating_time):
mecho_visited[nx][ny] = True
Q.append((nx, ny))
mecho_time[nx][ny] = mecho_time[x][y] + 1
# check if mecho reached a node surrounding his cave before the bees
for nx, ny in [(end[0] + 1, end[1]), (end[0] - 1, end[1]), (end[0], end[1] + 1), (end[0], end[1] - 1)]:
if valid_square(nx, ny) and mecho_reached(mecho_time[nx][ny], bees_time[nx][ny] - eating_time) and mecho_visited[nx][ny]:
return True
return False
def bs(lo, hi):
if lo > hi:
return -1
mid = (lo + hi) // 2
if not ok(mid):
return bs(lo, mid - 1)
elif mid < hi and ok(mid + 1):
return bs(mid + 1, hi)
else:
return mid
print(bs(0, n ** 2))
