import java.util.*;
class Main {
public static int mechoX;
public static int mechoY;
public static int denX;
public static int denY;
public static void main (String[]args) {
Scanner scan = new Scanner (System.in);
int sideLength = scan.nextInt();
int maxSteps = scan.nextInt();
char [][] grid = new char [sideLength][sideLength];
Queue <Pair> queue = new LinkedList <Pair>();
mechoX = 0;
mechoY = 0;
denX = 0;
denY = 0;
int [][] beeDistances = new int [sideLength][sideLength];
for (int i = 0; i < sideLength; i++) {
Arrays.fill(beeDistances[i], Integer.MAX_VALUE);
}
for (int i = 0; i < sideLength; i++) {
String line = scan.next();
for (int j = 0; j < sideLength; j++) {
grid[i][j] = line.charAt(j);
if (grid[i][j] == 'H') {
beeDistances[i][j] = 0;
Pair addingPair = new Pair (i, j);
queue.add(addingPair);
}
if (grid[i][j] == 'M') {
mechoX = i;
mechoY = j;
}
if (grid[i][j] == 'D') {
denX = i;
denY = j;
}
}
}
while (queue.isEmpty() == false) {
Pair curPair = queue.poll();
int curRow = curPair.row;
int curCol = curPair.column;
int cDist = beeDistances[curRow][curCol];
if ((curRow - 1 >= 0) && ((grid[curRow - 1][curCol] == 'G') || (grid[curRow - 1][curCol] == 'M'))) {
if (cDist + 1 < beeDistances[curRow - 1][curCol]) {
beeDistances[curRow - 1][curCol] = cDist + 1;
Pair addingPair = new Pair (curRow - 1, curCol);
queue.add(addingPair);
}
}
if ((curCol + 1 < sideLength) && ((grid[curRow][curCol + 1] == 'G') || (grid[curRow][curCol + 1] == 'M'))) {
if (cDist + 1 < beeDistances[curRow][curCol + 1]) {
beeDistances[curRow][curCol + 1] = cDist + 1;
Pair addingPair = new Pair (curRow, curCol + 1);
queue.add(addingPair);
}
}
if ((curRow + 1 < sideLength) && ((grid[curRow + 1][curCol] == 'G') || (grid[curRow + 1][curCol] == 'M'))) {
if (cDist + 1 < beeDistances[curRow + 1][curCol]) {
beeDistances[curRow + 1][curCol] = cDist + 1;
Pair addingPair = new Pair (curRow + 1, curCol);
queue.add(addingPair);
}
}
if ((curCol - 1 >= 0) && ((grid[curRow][curCol - 1] == 'G') || (grid[curRow][curCol - 1] == 'M'))) {
if (cDist + 1 < beeDistances[curRow][curCol - 1]) {
beeDistances[curRow][curCol - 1] = cDist + 1;
Pair addingPair = new Pair (curRow, curCol - 1);
queue.add(addingPair);
}
}
}
// Program works so far
int lowerBound = 0;
int upperBound = beeDistances[mechoX][mechoY];
int lastWorkingMiddle = -1;
int lastMiddle = -1;
while (lowerBound <= upperBound) {
int middle = (lowerBound + upperBound + 1) / 2;
if (lastMiddle == middle) {
break;
}
lastMiddle = middle;
if (bfsSimulation(middle, maxSteps, grid, beeDistances)) {
lowerBound = middle;
lastWorkingMiddle = middle;
}
else {
upperBound = middle;
}
}
if (bfsSimulation(0, maxSteps, grid, beeDistances)) {
lastWorkingMiddle = Math.max(lastWorkingMiddle, 0);
}
System.out.println(lastWorkingMiddle);
}
public static boolean bfsSimulation (int waitingTime, int maxSteps, char [][] grid, int [][] beeDistances) {
int sideLength = grid.length;
boolean [][] visited = new boolean [sideLength][sideLength];
boolean [][] workingVisited = new boolean [sideLength][sideLength];
Triplet startingPair = new Triplet (mechoX, mechoY, 0);
Queue <Triplet> queue = new LinkedList <Triplet>();
queue.add(startingPair);
visited[mechoX][mechoY] = true;
workingVisited[mechoX][mechoY] = true;
while (queue.isEmpty() == false) {
Triplet curTriplet = queue.poll();
int curX = curTriplet.row;
int curY = curTriplet.column;
int cDist = curTriplet.distance;
ArrayList<Pair> neighborsWithinOne = neighbors(curX, curY, maxSteps, grid);
for (int i = 0; i < neighborsWithinOne.size(); i++) {
Pair curPair = neighborsWithinOne.get(i);
int nextR = curPair.row;
int nextC = curPair.column;
boolean hasNeighbor = false;
if ((nextR - 1 >= 0) && (workingVisited[nextR - 1][nextC])) {
hasNeighbor = true;
}
if ((nextC + 1 < sideLength) && (workingVisited[nextR][nextC + 1])) {
hasNeighbor = true;
}
if ((nextR + 1 < sideLength) && (workingVisited[nextR + 1][nextC])) {
hasNeighbor = true;
}
if ((nextC - 1 >= 0) && (workingVisited[nextR][nextC - 1])) {
hasNeighbor = true;
}
if ((cDist + waitingTime < beeDistances[nextR][nextC]) && (visited[nextR][nextC] == false) && (hasNeighbor)) {
visited[nextR][nextC] = true;
Triplet addingTriplet = new Triplet (nextR, nextC, cDist + 1);
queue.add(addingTriplet);
workingVisited[nextR][nextC] = true;
}
else if (visited[nextR][nextC] == false) {
visited[nextR][nextC] = true;
}
}
}
return (workingVisited[denX][denY]);
}
public static ArrayList<Pair> neighbors (int startX, int startY, int maxSteps, char [][] grid) {
ArrayList<Pair> answerList = new ArrayList<Pair>();
Triplet startingPair = new Triplet (startX, startY, 0);
Queue <Triplet> queue = new LinkedList <Triplet>();
queue.add(startingPair);
int sideLength = grid.length;
boolean [][] visited = new boolean [sideLength][sideLength];
visited[startX][startY] = true;
while (queue.isEmpty() == false) {
Triplet curPair = queue.poll();
int curX = curPair.row;
int curY = curPair.column;
int cDist = curPair.distance;
if (cDist <= maxSteps) {
Pair addingPair = new Pair (curX, curY);
answerList.add(addingPair);
}
if (cDist == maxSteps) {
continue;
}
if ((curX - 1 >= 0) && (visited[curX - 1][curY] == false) && (((grid[curX - 1][curY] == 'G')) || (grid[curX - 1][curY] == 'D'))) {
Triplet addingTriplet = new Triplet (curX - 1, curY, cDist + 1);
queue.add(addingTriplet);
visited[curX - 1][curY] = true;
}
if ((curY + 1 < sideLength) && (visited[curX][curY + 1] == false) && ((grid[curX][curY + 1] == 'G') || (grid[curX][curY + 1] == 'D'))) {
Triplet addingTriplet = new Triplet (curX, curY + 1, cDist + 1);
queue.add(addingTriplet);
visited[curX][curY + 1] = true;
}
if ((curX + 1 < sideLength) && (visited[curX + 1][curY] == false) && ((grid[curX + 1][curY] == 'G') || (grid[curX + 1][curY] == 'D'))) {
Triplet addingTriplet = new Triplet (curX + 1, curY, cDist + 1);
queue.add(addingTriplet);
visited[curX + 1][curY] = true;
}
if ((curY - 1 >= 0) && (visited[curX][curY - 1] == false) && ((grid[curX][curY - 1] == 'G') || (grid[curX][curY - 1] == 'D'))) {
Triplet addingTriplet = new Triplet (curX, curY - 1, cDist + 1);
queue.add(addingTriplet);
visited[curX][curY - 1] = true;
}
}
return (answerList);
}
private static class Triplet {
int row;
int column;
int distance;
public Triplet (int row, int column, int distance) {
this.row = row;
this.column = column;
this.distance = distance;
}
}
private static class Pair {
int row;
int column;
public Pair (int row, int column) {
this.row = row;
this.column = column;
}
}
}
