답안 #815872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
815872	2023-08-09T01:50:13 Z	powervic08	Mecho (IOI09_mecho)	Java 11	4 / 100	824 ms	47780 KB

mecho

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] == 0) {
                        q.add(new Node(newi, newj, p.dist + S));
                    }
                }
            }
        }
        grid[endi][endj] = Integer.MAX_VALUE;
        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] == 0 && dists[newi][newj] > p.dist + 1 || newi == endi && newj == endj && dists[newi][newj] == p.dist + 1) {
                        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;
        }
    }

}

Subtask #1

4.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	49 ms	8372 KB	Output isn't correct
2	Incorrect	47 ms	8492 KB	Output isn't correct
3	Incorrect	61 ms	8252 KB	Output isn't correct
4	Incorrect	64 ms	8464 KB	Output isn't correct
5	Incorrect	51 ms	8356 KB	Output isn't correct
6	Incorrect	64 ms	8400 KB	Output isn't correct
7	Incorrect	694 ms	33212 KB	Output isn't correct
8	Correct	65 ms	8440 KB	Output is correct
9	Incorrect	68 ms	8312 KB	Output isn't correct
10	Incorrect	60 ms	8364 KB	Output isn't correct
11	Incorrect	51 ms	8548 KB	Output isn't correct
12	Incorrect	57 ms	8720 KB	Output isn't correct
13	Incorrect	82 ms	9180 KB	Output isn't correct
14	Correct	128 ms	12424 KB	Output is correct
15	Incorrect	78 ms	8360 KB	Output isn't correct
16	Incorrect	56 ms	8268 KB	Output isn't correct
17	Incorrect	59 ms	8332 KB	Output isn't correct
18	Incorrect	54 ms	8804 KB	Output isn't correct
19	Incorrect	69 ms	8644 KB	Output isn't correct
20	Incorrect	85 ms	10368 KB	Output isn't correct
21	Incorrect	98 ms	10680 KB	Output isn't correct
22	Incorrect	91 ms	10988 KB	Output isn't correct
23	Incorrect	84 ms	11056 KB	Output isn't correct
24	Incorrect	102 ms	11780 KB	Output isn't correct
25	Incorrect	101 ms	11664 KB	Output isn't correct
26	Incorrect	103 ms	12480 KB	Output isn't correct
27	Incorrect	106 ms	12416 KB	Output isn't correct
28	Incorrect	109 ms	12364 KB	Output isn't correct
29	Incorrect	84 ms	12376 KB	Output isn't correct
30	Incorrect	98 ms	12936 KB	Output isn't correct
31	Incorrect	99 ms	12608 KB	Output isn't correct
32	Incorrect	134 ms	12700 KB	Output isn't correct
33	Incorrect	229 ms	14756 KB	Output isn't correct
34	Incorrect	268 ms	14892 KB	Output isn't correct
35	Incorrect	251 ms	15804 KB	Output isn't correct
36	Incorrect	248 ms	17300 KB	Output isn't correct
37	Incorrect	295 ms	17820 KB	Output isn't correct
38	Incorrect	341 ms	16736 KB	Output isn't correct
39	Incorrect	265 ms	18840 KB	Output isn't correct
40	Incorrect	311 ms	18824 KB	Output isn't correct
41	Incorrect	315 ms	17268 KB	Output isn't correct
42	Incorrect	263 ms	19248 KB	Output isn't correct
43	Incorrect	316 ms	19072 KB	Output isn't correct
44	Incorrect	398 ms	18068 KB	Output isn't correct
45	Incorrect	319 ms	19372 KB	Output isn't correct
46	Incorrect	345 ms	19204 KB	Output isn't correct
47	Incorrect	428 ms	18896 KB	Output isn't correct
48	Incorrect	293 ms	20160 KB	Output isn't correct
49	Incorrect	383 ms	20636 KB	Output isn't correct
50	Incorrect	421 ms	19480 KB	Output isn't correct
51	Incorrect	307 ms	22272 KB	Output isn't correct
52	Incorrect	406 ms	22112 KB	Output isn't correct
53	Incorrect	477 ms	20644 KB	Output isn't correct
54	Incorrect	367 ms	23812 KB	Output isn't correct
55	Incorrect	426 ms	23796 KB	Output isn't correct
56	Incorrect	456 ms	22780 KB	Output isn't correct
57	Incorrect	396 ms	25800 KB	Output isn't correct
58	Incorrect	483 ms	25564 KB	Output isn't correct
59	Incorrect	560 ms	25120 KB	Output isn't correct
60	Incorrect	379 ms	27092 KB	Output isn't correct
61	Incorrect	598 ms	27020 KB	Output isn't correct
62	Incorrect	655 ms	25844 KB	Output isn't correct
63	Incorrect	403 ms	25604 KB	Output isn't correct
64	Incorrect	625 ms	26164 KB	Output isn't correct
65	Incorrect	561 ms	26236 KB	Output isn't correct
66	Incorrect	498 ms	25768 KB	Output isn't correct
67	Correct	411 ms	25924 KB	Output is correct
68	Incorrect	297 ms	25008 KB	Output isn't correct
69	Incorrect	316 ms	25016 KB	Output isn't correct
70	Incorrect	309 ms	24652 KB	Output isn't correct
71	Incorrect	283 ms	24060 KB	Output isn't correct
72	Incorrect	344 ms	25820 KB	Output isn't correct
73	Incorrect	434 ms	47592 KB	Output isn't correct
74	Incorrect	750 ms	47780 KB	Output isn't correct
75	Incorrect	623 ms	47684 KB	Output isn't correct
76	Incorrect	580 ms	47688 KB	Output isn't correct
77	Incorrect	618 ms	47596 KB	Output isn't correct
78	Correct	655 ms	44380 KB	Output is correct
79	Incorrect	791 ms	44616 KB	Output isn't correct
80	Incorrect	591 ms	44444 KB	Output isn't correct
81	Incorrect	596 ms	44436 KB	Output isn't correct
82	Incorrect	628 ms	44492 KB	Output isn't correct
83	Incorrect	664 ms	40268 KB	Output isn't correct
84	Incorrect	824 ms	40380 KB	Output isn't correct
85	Incorrect	599 ms	40428 KB	Output isn't correct
86	Incorrect	628 ms	40324 KB	Output isn't correct
87	Incorrect	613 ms	40448 KB	Output isn't correct
88	Incorrect	598 ms	36588 KB	Output isn't correct
89	Incorrect	808 ms	36596 KB	Output isn't correct
90	Incorrect	680 ms	36472 KB	Output isn't correct
91	Incorrect	722 ms	36524 KB	Output isn't correct
92	Incorrect	657 ms	36600 KB	Output isn't correct