import java.util.*;
import java.io.*;
public class Mecho {
public static void main(String[] args) throws IOException {
Reader in = new Reader();
PrintWriter out = new PrintWriter(System.out);
int N = in.nextInt(), K = in.nextInt();
char[][] mat = new char[N][N];
for (int i = 0; i < N; i++) {
mat[i] = in.next().toCharArray();
}
Queue<int[]> q = new LinkedList<>();
int[][] bee = new int[N][N];
int[] start = new int[2], end = new int[2];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (mat[i][j] == 'H') {
bee[i][j] = 0;
q.offer(new int[]{i, j});
} else {
bee[i][j] = -1;
}
if (mat[i][j] == 'M') {
start = new int[]{i, j};
}
if (mat[i][j] == 'D') {
end = new int[]{i, j};
}
}
}
int[] x = new int[]{-1, 1, 0, 0}, y = new int[]{0, 0, -1, 1};
while (!q.isEmpty()) {
int[] current = q.poll();
int r = current[0], c = current[1];
for (int k = 0; k < 4; k++) {
int r2 = r + x[k], c2 = c + y[k];
if (r2 >= 0 && r2 < N && c2 >= 0 && c2 < N) {
if (mat[r2][c2] != 'D' && mat[r2][c2] != 'T' && bee[r2][c2] == -1) {
bee[r2][c2] = bee[r][c] + 1;
q.offer(new int[]{r2, c2});
}
}
}
}
out.println(search(mat, bee, start, end, K, 0, bee[start[0]][start[1]] - 1));
out.close();
}
public static int search(char[][] mat, int[][] bee, int[] start, int[] end, int K, int l, int r) {
if (l > r) {
return -1;
}
int mid = (l + r) / 2;
if (check(mat, bee, start, end, K, mid)) {
int m = search(mat, bee, start, end, K, mid + 1, r);
if (m == -1) {
return mid;
}
return m;
}
return search(mat, bee, start, end, K, l, mid - 1);
}
public static boolean check(char[][] mat, int[][] bee, int[] start, int[] end, int K, int eat) {
int N = mat.length;
int[][] dist = new int[N][N];
for (int i = 0; i < N; i++) {
Arrays.fill(dist[i], -1);
}
dist[start[0]][start[1]] = 0;
Queue<int[]> q = new LinkedList<>();
q.offer(start);
int[] x = new int[]{-1, 1, 0, 0}, y = new int[]{0, 0, -1, 1};
while (!q.isEmpty()) {
int[] current = q.poll();
int r = current[0], c = current[1];
for (int k = 0; k < 4; k++) {
int r2 = r + x[k], c2 = c + y[k];
if (r2 >= 0 && r2 < N && c2 >= 0 && c2 < N) {
if (mat[r2][c2] != 'T' && mat[r2][c2] != 'H' && dist[r2][c2] == -1) {
if (bee[r2][c2] == -1 || (dist[r][c] + 1) / K + eat < bee[r2][c2]) {
dist[r2][c2] = dist[r][c] + 1;
q.offer(new int[]{r2, c2});
}
}
}
}
}
return dist[end[0]][end[1]] >= 0;
}
static class Reader {
BufferedInputStream in;
public Reader() {
in = new BufferedInputStream(System.in);
}
public String nextLine() throws IOException {
int c;
StringBuilder sb = new StringBuilder("");
while ((c = in.read()) != '\n')
sb.append((char)(c));
return sb.toString();
}
public String next() throws IOException {
int c;
StringBuilder sb = new StringBuilder("");
while ((c = in.read()) != ' ' && c != '\n')
sb.append((char)(c));
return sb.toString();
}
public int nextInt() throws IOException {
return (int)nextLong();
}
public long nextLong() throws IOException {
int c;
long res = 0;
boolean start = false, negative = false;
while ((c = in.read()) != ' ' && c != '\n' || !start)
if (c >= '0' && c <= '9' || c == '-') {
start = true;
if (c == '-')
negative = true;
else
res = res * 10 + c - '0';
}
return res * (negative ? -1 : 1);
}
}
public static void sort(int[] arr) {
List<Integer> list = new ArrayList<>();
for (int i : arr) {
list.add(i);
}
Collections.sort(list);
for (int i = 0; i < arr.length; i++) {
arr[i] = list.get(i);
}
}
}
Compilation message
mecho.java:3: error: class Mecho is public, should be declared in a file named Mecho.java
public class Mecho {
^
1 error
