답안 #815899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
815899	2023-08-09T02:09:03 Z	powervic08	Mecho (IOI09_mecho)	Java 11	95 / 100	599 ms	47812 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] != 2) {
                        q.add(new Node(newi, newj, p.dist + S));
                    }
                }
            }
        }
        dists[endi][endj] = Integer.MAX_VALUE;
        int l = -1;
        int r = 2 * n * n;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (works(mid, dists, grid, starti, startj, endi, endj)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        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<>();
        if ((long) mid * S >= dists[starti][startj])
            return false;
        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 && !visited[newi][newj]) {
                        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

95.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	8316 KB	Output is correct
2	Correct	47 ms	8580 KB	Output is correct
3	Correct	47 ms	8464 KB	Output is correct
4	Correct	47 ms	8552 KB	Output is correct
5	Correct	48 ms	8508 KB	Output is correct
6	Correct	48 ms	8512 KB	Output is correct
7	Correct	513 ms	32916 KB	Output is correct
8	Correct	58 ms	8212 KB	Output is correct
9	Correct	50 ms	8348 KB	Output is correct
10	Correct	49 ms	8360 KB	Output is correct
11	Correct	58 ms	8248 KB	Output is correct
12	Incorrect	59 ms	8688 KB	Output isn't correct
13	Correct	67 ms	8940 KB	Output is correct
14	Correct	118 ms	11876 KB	Output is correct
15	Correct	48 ms	8444 KB	Output is correct
16	Correct	48 ms	8560 KB	Output is correct
17	Correct	49 ms	8736 KB	Output is correct
18	Correct	49 ms	8340 KB	Output is correct
19	Correct	49 ms	8576 KB	Output is correct
20	Correct	50 ms	8532 KB	Output is correct
21	Correct	57 ms	8532 KB	Output is correct
22	Correct	52 ms	8832 KB	Output is correct
23	Correct	54 ms	8904 KB	Output is correct
24	Correct	67 ms	8720 KB	Output is correct
25	Correct	57 ms	8836 KB	Output is correct
26	Correct	59 ms	8748 KB	Output is correct
27	Correct	64 ms	8628 KB	Output is correct
28	Correct	68 ms	8720 KB	Output is correct
29	Correct	65 ms	8844 KB	Output is correct
30	Correct	63 ms	8872 KB	Output is correct
31	Correct	69 ms	10188 KB	Output is correct
32	Correct	64 ms	8900 KB	Output is correct
33	Correct	148 ms	14812 KB	Output is correct
34	Correct	203 ms	15048 KB	Output is correct
35	Correct	242 ms	16004 KB	Output is correct
36	Correct	143 ms	15188 KB	Output is correct
37	Correct	203 ms	15324 KB	Output is correct
38	Correct	257 ms	16672 KB	Output is correct
39	Correct	174 ms	15788 KB	Output is correct
40	Correct	210 ms	15688 KB	Output is correct
41	Correct	280 ms	17568 KB	Output is correct
42	Correct	149 ms	16060 KB	Output is correct
43	Correct	226 ms	16476 KB	Output is correct
44	Correct	295 ms	18680 KB	Output is correct
45	Correct	157 ms	16416 KB	Output is correct
46	Correct	200 ms	16668 KB	Output is correct
47	Correct	325 ms	19224 KB	Output is correct
48	Correct	158 ms	16788 KB	Output is correct
49	Correct	234 ms	17248 KB	Output is correct
50	Correct	358 ms	19996 KB	Output is correct
51	Correct	173 ms	17348 KB	Output is correct
52	Correct	205 ms	17540 KB	Output is correct
53	Correct	416 ms	20968 KB	Output is correct
54	Correct	160 ms	18232 KB	Output is correct
55	Correct	227 ms	18140 KB	Output is correct
56	Correct	415 ms	23756 KB	Output is correct
57	Correct	185 ms	18964 KB	Output is correct
58	Correct	243 ms	20824 KB	Output is correct
59	Correct	426 ms	25292 KB	Output is correct
60	Correct	182 ms	20640 KB	Output is correct
61	Correct	229 ms	21044 KB	Output is correct
62	Correct	456 ms	25868 KB	Output is correct
63	Correct	380 ms	25360 KB	Output is correct
64	Correct	530 ms	26180 KB	Output is correct
65	Correct	478 ms	26000 KB	Output is correct
66	Correct	422 ms	25936 KB	Output is correct
67	Correct	383 ms	26076 KB	Output is correct
68	Correct	274 ms	23776 KB	Output is correct
69	Correct	300 ms	23924 KB	Output is correct
70	Correct	292 ms	22132 KB	Output is correct
71	Correct	288 ms	22504 KB	Output is correct
72	Correct	244 ms	21448 KB	Output is correct
73	Correct	385 ms	47656 KB	Output is correct
74	Correct	488 ms	47496 KB	Output is correct
75	Correct	553 ms	47468 KB	Output is correct
76	Correct	498 ms	47616 KB	Output is correct
77	Correct	521 ms	47812 KB	Output is correct
78	Correct	599 ms	44500 KB	Output is correct
79	Correct	508 ms	44368 KB	Output is correct
80	Correct	494 ms	44488 KB	Output is correct
81	Correct	564 ms	44648 KB	Output is correct
82	Correct	540 ms	44332 KB	Output is correct
83	Correct	533 ms	40524 KB	Output is correct
84	Correct	474 ms	40520 KB	Output is correct
85	Correct	518 ms	40584 KB	Output is correct
86	Correct	485 ms	40468 KB	Output is correct
87	Correct	522 ms	40428 KB	Output is correct
88	Correct	509 ms	36772 KB	Output is correct
89	Correct	534 ms	36724 KB	Output is correct
90	Correct	500 ms	36840 KB	Output is correct
91	Correct	534 ms	37084 KB	Output is correct
92	Correct	567 ms	36796 KB	Output is correct