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 - 1));
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;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
49 ms |
8460 KB |
Output isn't correct |
2 |
Correct |
49 ms |
8216 KB |
Output is correct |
3 |
Incorrect |
50 ms |
8332 KB |
Output isn't correct |
4 |
Correct |
47 ms |
8368 KB |
Output is correct |
5 |
Correct |
56 ms |
8468 KB |
Output is correct |
6 |
Correct |
49 ms |
8548 KB |
Output is correct |
7 |
Correct |
585 ms |
32948 KB |
Output is correct |
8 |
Incorrect |
49 ms |
8636 KB |
Output isn't correct |
9 |
Correct |
50 ms |
8712 KB |
Output is correct |
10 |
Correct |
49 ms |
8504 KB |
Output is correct |
11 |
Correct |
50 ms |
8604 KB |
Output is correct |
12 |
Incorrect |
57 ms |
8808 KB |
Output isn't correct |
13 |
Incorrect |
63 ms |
9164 KB |
Output isn't correct |
14 |
Correct |
99 ms |
12544 KB |
Output is correct |
15 |
Incorrect |
48 ms |
8632 KB |
Output isn't correct |
16 |
Correct |
50 ms |
8504 KB |
Output is correct |
17 |
Incorrect |
49 ms |
8492 KB |
Output isn't correct |
18 |
Correct |
50 ms |
8604 KB |
Output is correct |
19 |
Incorrect |
55 ms |
8604 KB |
Output isn't correct |
20 |
Correct |
50 ms |
8616 KB |
Output is correct |
21 |
Incorrect |
55 ms |
8364 KB |
Output isn't correct |
22 |
Correct |
53 ms |
8480 KB |
Output is correct |
23 |
Incorrect |
55 ms |
8740 KB |
Output isn't correct |
24 |
Correct |
61 ms |
8828 KB |
Output is correct |
25 |
Incorrect |
57 ms |
8684 KB |
Output isn't correct |
26 |
Correct |
63 ms |
8944 KB |
Output is correct |
27 |
Incorrect |
72 ms |
8824 KB |
Output isn't correct |
28 |
Correct |
67 ms |
8996 KB |
Output is correct |
29 |
Incorrect |
60 ms |
8852 KB |
Output isn't correct |
30 |
Correct |
64 ms |
8952 KB |
Output is correct |
31 |
Incorrect |
73 ms |
10436 KB |
Output isn't correct |
32 |
Correct |
78 ms |
11204 KB |
Output is correct |
33 |
Incorrect |
152 ms |
14820 KB |
Output isn't correct |
34 |
Correct |
218 ms |
14844 KB |
Output is correct |
35 |
Correct |
265 ms |
16276 KB |
Output is correct |
36 |
Incorrect |
147 ms |
15056 KB |
Output isn't correct |
37 |
Correct |
206 ms |
15508 KB |
Output is correct |
38 |
Correct |
291 ms |
16588 KB |
Output is correct |
39 |
Incorrect |
149 ms |
15956 KB |
Output isn't correct |
40 |
Correct |
209 ms |
15876 KB |
Output is correct |
41 |
Correct |
315 ms |
17588 KB |
Output is correct |
42 |
Incorrect |
158 ms |
16000 KB |
Output isn't correct |
43 |
Correct |
215 ms |
16184 KB |
Output is correct |
44 |
Correct |
365 ms |
18572 KB |
Output is correct |
45 |
Incorrect |
154 ms |
16520 KB |
Output isn't correct |
46 |
Correct |
209 ms |
16448 KB |
Output is correct |
47 |
Correct |
397 ms |
19228 KB |
Output is correct |
48 |
Incorrect |
155 ms |
16832 KB |
Output isn't correct |
49 |
Correct |
214 ms |
17128 KB |
Output is correct |
50 |
Correct |
410 ms |
19820 KB |
Output is correct |
51 |
Incorrect |
155 ms |
17488 KB |
Output isn't correct |
52 |
Correct |
217 ms |
18008 KB |
Output is correct |
53 |
Correct |
456 ms |
21212 KB |
Output is correct |
54 |
Incorrect |
157 ms |
18136 KB |
Output isn't correct |
55 |
Correct |
224 ms |
18836 KB |
Output is correct |
56 |
Correct |
478 ms |
23352 KB |
Output is correct |
57 |
Incorrect |
168 ms |
18792 KB |
Output isn't correct |
58 |
Correct |
235 ms |
21040 KB |
Output is correct |
59 |
Correct |
551 ms |
25632 KB |
Output is correct |
60 |
Incorrect |
173 ms |
20492 KB |
Output isn't correct |
61 |
Correct |
240 ms |
21688 KB |
Output is correct |
62 |
Correct |
603 ms |
25868 KB |
Output is correct |
63 |
Correct |
377 ms |
25724 KB |
Output is correct |
64 |
Correct |
592 ms |
26564 KB |
Output is correct |
65 |
Correct |
496 ms |
26372 KB |
Output is correct |
66 |
Incorrect |
448 ms |
26264 KB |
Output isn't correct |
67 |
Correct |
417 ms |
25820 KB |
Output is correct |
68 |
Correct |
297 ms |
25256 KB |
Output is correct |
69 |
Correct |
296 ms |
24764 KB |
Output is correct |
70 |
Correct |
294 ms |
23444 KB |
Output is correct |
71 |
Correct |
277 ms |
24656 KB |
Output is correct |
72 |
Incorrect |
270 ms |
21792 KB |
Output isn't correct |
73 |
Incorrect |
430 ms |
47700 KB |
Output isn't correct |
74 |
Correct |
503 ms |
47672 KB |
Output is correct |
75 |
Correct |
541 ms |
47704 KB |
Output is correct |
76 |
Correct |
538 ms |
47924 KB |
Output is correct |
77 |
Correct |
518 ms |
47692 KB |
Output is correct |
78 |
Correct |
585 ms |
44364 KB |
Output is correct |
79 |
Correct |
483 ms |
44504 KB |
Output is correct |
80 |
Correct |
484 ms |
44656 KB |
Output is correct |
81 |
Correct |
542 ms |
44684 KB |
Output is correct |
82 |
Correct |
538 ms |
44496 KB |
Output is correct |
83 |
Correct |
593 ms |
40492 KB |
Output is correct |
84 |
Correct |
550 ms |
40640 KB |
Output is correct |
85 |
Correct |
570 ms |
40620 KB |
Output is correct |
86 |
Correct |
565 ms |
40588 KB |
Output is correct |
87 |
Correct |
563 ms |
40672 KB |
Output is correct |
88 |
Correct |
618 ms |
36808 KB |
Output is correct |
89 |
Correct |
599 ms |
36704 KB |
Output is correct |
90 |
Correct |
661 ms |
36708 KB |
Output is correct |
91 |
Correct |
589 ms |
36828 KB |
Output is correct |
92 |
Correct |
649 ms |
36768 KB |
Output is correct |