import java.util.*;
import java.io.*;
public class Mecho {
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int S;
public static void main(String[] args) throws IOException {
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
StringTokenizer st = new StringTokenizer(f.readLine());
int n = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
int[][] grid = new int[n][n];
int starti = 0, startj = 0, endi = 0, endj = 0;
for (int i = 0; i < n; i++) {
String s = f.readLine();
for (int j = 0; j < n; j++) {
if (s.charAt(j) == 'H') grid[i][j] = 1;
else if (s.charAt(j) == 'T') grid[i][j] = 2;
else if (s.charAt(j) == 'M') {
starti = i;
startj = j;
} else if (s.charAt(j) == 'D') {
endi = i;
endj = j;
}
}
}
out.println(maximumMinutes(grid, starti, startj, endi, endj));
out.close();
f.close();
}
public static int maximumMinutes(int[][] grid, int starti, int startj, int endi, int endj) {
int n = grid.length;
int m = grid[0].length;
Queue<Node> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) {
q.add(new Node(i, j, 0));
}
}
}
int[][] dists = new int[n][m];
for (int i = 0; i < n; i++) {
Arrays.fill(dists[i], Integer.MAX_VALUE);
}
while (!q.isEmpty()) {
Node p = q.poll();
if (p.dist >= dists[p.i][p.j]) {
continue;
}
dists[p.i][p.j] = (int) p.dist;
for (int i = 0; i < 4; i++) {
int newi = dx[i] + p.i;
int newj = dy[i] + p.j;
if (inRange(newi, newj, grid)) {
if (grid[newi][newj] != 2) {
q.add(new Node(newi, newj, p.dist + 1));
}
}
}
}
int l = -1;
int r = n * n;
while (l < r) {
int mid = (l + r + 1) / 2;
if (works(mid, dists, grid, starti, startj, endi, endj)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
public static boolean works(int mid, int[][] dists, int[][] grid, int starti, int startj, int endi, int endj) {
Queue<Node> q = new LinkedList<>();
q.add(new Node(starti, startj, (long) mid * S));
boolean[][] visited = new boolean[grid.length][grid[0].length];
while (!q.isEmpty()) {
Node p = q.poll();
if (p.i == endi && p.j == endj) {
return true;
}
if (visited[p.i][p.j]) {
continue;
}
visited[p.i][p.j] = true;
for (int i = 0; i < 4; i++) {
int newi = dx[i] + p.i;
int newj = dy[i] + p.j;
if (inRange(newi, newj, grid)) {
if (grid[newi][newj] != 2 && dists[newi][newj] > (p.dist + 1) / S || newi == endi && newj == endj && dists[newi][newj] == (p.dist + 1) / S) {
q.add(new Node(newi, newj, p.dist + 1));
}
}
}
}
return false;
}
public static boolean inRange(int i, int j, int[][] grid) {
return i >= 0 && j >= 0 && i < grid.length && j < grid[0].length;
}
static class Node {
int i, j;
long dist;
public Node(int a, int b, long c) {
i = a;
j = b;
dist = c;
}
}
}
Compilation message
mecho.cpp:1:1: error: 'import' does not name a type
1 | import java.util.*;
| ^~~~~~
mecho.cpp:2:1: error: 'import' does not name a type
2 | import java.io.*;
| ^~~~~~
mecho.cpp:4:1: error: expected unqualified-id before 'public'
4 | public class Mecho {
| ^~~~~~
