import java.io.*;
import java.util.*;
public class Main {
static int N, S;
static int[][] distFromHive;
static int startX, startY, endX, endY;
static int[] dX, dY;
static boolean[][] forest;
public static void main(String[] args) throws IOException, FileNotFoundException {
Scanner in = new Scanner(System.in);
// Scanner in = new Scanner(new File("test.in"));
N = in.nextInt();
S = in.nextInt();
forest = new boolean[N][N];
PriorityQueue<State> pq = new PriorityQueue<>();
for(int i = 0; i < N; i++){
String line = in.next();
for(int j = 0; j < N; j++){
int cchar = line.charAt(j);
if(cchar == 'T'){
forest[i][j] = true;
} else if (cchar == 'M'){
startX = i;
startY = j;
} else if (cchar == 'D'){
endX = i;
endY = j;
} else if (cchar == 'H'){
pq.add(new State(i, j, 0));
}
}
}
distFromHive = new int[N][N];
for(int i = 0; i < N; i++){
Arrays.fill(distFromHive[i], -1);
}
dX = new int[] {-1, 1, 0, 0};
dY = new int[] {0, 0, -1, 1};
while(!pq.isEmpty()){
State curr = pq.poll();
if(distFromHive[curr.x][curr.y] != -1){
continue;
}
distFromHive[curr.x][curr.y] = curr.dist;
for(int i = 0; i < 4; i++){
int nX = curr.x + dX[i];
int nY = curr.y + dY[i];
if(nX < 0 || nX >= N || nY < 0 || nY >= N || forest[nX][nY]){
continue;
}
pq.add(new State(nX, nY, curr.dist + 1));
}
}
// for(int i = 0; i < N; i++){
// System.out.println(Arrays.toString(distFromHive[i]));
// }
int a = 0;
int b = 1000000;
while(a != b){
int mid = (a + b + 1)/2;
if(works(mid)){
a = mid;
} else {
b = mid - 1;
}
}
System.out.println(a);
}
public static boolean works(int wait){
PriorityQueue<State> pq = new PriorityQueue<>();
pq.add(new State(startX, startY, wait * S));
boolean[][] visited = new boolean[N][N];
while(!pq.isEmpty()){
State curr = pq.poll();
if(visited[curr.x][curr.y]){
continue;
}
if(curr.x == endX && curr.y == endY){
// System.out.println("get to " + curr.x + " " + curr.y + " in " + curr.dist + " vs. " + distFromHive[curr.x][curr.y]);
return true;
}
if(distFromHive[curr.x][curr.y] * S <= curr.dist){
continue;
}
for(int i = 0; i < 4; i++){
int nX = curr.x + dX[i];
int nY = curr.y + dY[i];
if(nX < 0 || nX >= N || nY < 0 || nY >= N || forest[nX][nY]){
continue;
}
pq.add(new State(nX, nY, curr.dist + 1));
}
}
return false;
}
public static class State implements Comparable<State>{
int x, y, dist;
public State(int x, int y, int dist){
this.x = x;
this.y = y;
this.dist = dist;
}
public int compareTo(State s){
return dist - s.dist;
}
}
}
Compilation message
mecho.java:4: error: class Main is public, should be declared in a file named Main.java
public class Main {
^
1 error
