답안 #815862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
815862	2023-08-09T01:39:46 Z	powervic08	Mecho (IOI09_mecho)	Java 11	77 / 100	675 ms	47844 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 + 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] == 0 && 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;
        }
    }

}

Subtask #1

77.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	8520 KB	Output is correct
2	Incorrect	48 ms	8544 KB	Output isn't correct
3	Correct	48 ms	8352 KB	Output is correct
4	Incorrect	55 ms	8320 KB	Output isn't correct
5	Correct	49 ms	8284 KB	Output is correct
6	Incorrect	49 ms	8468 KB	Output isn't correct
7	Correct	586 ms	32932 KB	Output is correct
8	Correct	53 ms	8380 KB	Output is correct
9	Correct	49 ms	8612 KB	Output is correct
10	Correct	49 ms	8672 KB	Output is correct
11	Correct	49 ms	8420 KB	Output is correct
12	Incorrect	62 ms	8772 KB	Output isn't correct
13	Incorrect	67 ms	9088 KB	Output isn't correct
14	Correct	107 ms	12492 KB	Output is correct
15	Correct	54 ms	8528 KB	Output is correct
16	Correct	50 ms	8296 KB	Output is correct
17	Correct	49 ms	8568 KB	Output is correct
18	Correct	54 ms	8776 KB	Output is correct
19	Correct	51 ms	8364 KB	Output is correct
20	Correct	52 ms	8500 KB	Output is correct
21	Correct	53 ms	8528 KB	Output is correct
22	Correct	60 ms	8652 KB	Output is correct
23	Correct	55 ms	8848 KB	Output is correct
24	Correct	57 ms	8528 KB	Output is correct
25	Correct	57 ms	9040 KB	Output is correct
26	Correct	59 ms	8848 KB	Output is correct
27	Correct	59 ms	8576 KB	Output is correct
28	Correct	71 ms	9060 KB	Output is correct
29	Correct	72 ms	8812 KB	Output is correct
30	Correct	65 ms	9060 KB	Output is correct
31	Correct	68 ms	10488 KB	Output is correct
32	Correct	80 ms	11000 KB	Output is correct
33	Correct	142 ms	14828 KB	Output is correct
34	Correct	213 ms	15108 KB	Output is correct
35	Correct	260 ms	16076 KB	Output is correct
36	Correct	144 ms	15252 KB	Output is correct
37	Correct	217 ms	15316 KB	Output is correct
38	Correct	270 ms	16524 KB	Output is correct
39	Correct	147 ms	15676 KB	Output is correct
40	Correct	210 ms	15928 KB	Output is correct
41	Correct	313 ms	17884 KB	Output is correct
42	Correct	151 ms	15896 KB	Output is correct
43	Correct	213 ms	16092 KB	Output is correct
44	Correct	350 ms	18572 KB	Output is correct
45	Correct	156 ms	16432 KB	Output is correct
46	Correct	211 ms	16484 KB	Output is correct
47	Correct	382 ms	19140 KB	Output is correct
48	Correct	153 ms	17000 KB	Output is correct
49	Correct	223 ms	17180 KB	Output is correct
50	Correct	428 ms	19632 KB	Output is correct
51	Correct	167 ms	17412 KB	Output is correct
52	Correct	230 ms	17924 KB	Output is correct
53	Correct	442 ms	21188 KB	Output is correct
54	Correct	163 ms	18076 KB	Output is correct
55	Correct	227 ms	19044 KB	Output is correct
56	Correct	484 ms	23440 KB	Output is correct
57	Correct	168 ms	19008 KB	Output is correct
58	Correct	248 ms	21160 KB	Output is correct
59	Correct	528 ms	25556 KB	Output is correct
60	Correct	166 ms	20532 KB	Output is correct
61	Correct	226 ms	21548 KB	Output is correct
62	Correct	606 ms	25696 KB	Output is correct
63	Correct	369 ms	25560 KB	Output is correct
64	Correct	579 ms	26768 KB	Output is correct
65	Correct	491 ms	26212 KB	Output is correct
66	Correct	438 ms	25824 KB	Output is correct
67	Correct	408 ms	26044 KB	Output is correct
68	Correct	276 ms	25280 KB	Output is correct
69	Correct	306 ms	24736 KB	Output is correct
70	Correct	276 ms	23748 KB	Output is correct
71	Correct	284 ms	24796 KB	Output is correct
72	Incorrect	263 ms	22084 KB	Output isn't correct
73	Incorrect	432 ms	47628 KB	Output isn't correct
74	Correct	514 ms	47692 KB	Output is correct
75	Correct	555 ms	47612 KB	Output is correct
76	Correct	530 ms	47844 KB	Output is correct
77	Correct	525 ms	47524 KB	Output is correct
78	Correct	631 ms	44588 KB	Output is correct
79	Correct	492 ms	44496 KB	Output is correct
80	Correct	516 ms	44704 KB	Output is correct
81	Correct	558 ms	44372 KB	Output is correct
82	Correct	511 ms	44576 KB	Output is correct
83	Correct	594 ms	40480 KB	Output is correct
84	Correct	562 ms	40448 KB	Output is correct
85	Correct	605 ms	40492 KB	Output is correct
86	Correct	569 ms	40460 KB	Output is correct
87	Correct	581 ms	40520 KB	Output is correct
88	Correct	592 ms	36796 KB	Output is correct
89	Correct	595 ms	36784 KB	Output is correct
90	Correct	675 ms	36780 KB	Output is correct
91	Correct	609 ms	36824 KB	Output is correct
92	Correct	672 ms	36948 KB	Output is correct