oj.uz

답안 #794900

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
794900 2023-07-27T02:13:19 Z sushikid Mecho (IOI09_mecho) Java 11
23 / 100
 155 ms 65536 KB 
import java.util.*;
import java.io.*;

public class mecho {
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};

    private static int n;
    private static char[][] grid;

    private static boolean mark(int x, int y, boolean[][] arr){
        for (int i = 0; i < 4; i++) {
            int fx = x + dx[i];
            int fy = y + dy[i];
            if(check(fx, fy) && arr[fx][fy]){
                return true;
            }
        }
        return arr[x][y];
    }
    private static boolean check(int x, int y){
        return 0 <= x && x < n && 0 <= y && y < n;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(r.readLine());
        n = Integer.parseInt(st.nextToken()); int s = Integer.parseInt(st.nextToken());

        grid = new char[n][n];
        int[] start = {-1, -1}; int[] end = {-1, -1};
        Queue<int[]> hives = new LinkedList<>();
        int ans = -1;
        boolean[][][] times = new boolean[2 * n][n][n];

        for (int i = 0; i < n; i++) {
            String str = r.readLine();
            for (int j = 0; j < n; j++) {
                if(str.charAt(j) == 'M'){
                    start = new int[]{i, j};
                }
                if(str.charAt(j) == 'D'){
                    end = new int[]{i, j};
                }
                if(str.charAt(j) == 'H'){
                    hives.add(new int[]{i, j, 0});
                    times[0][i][j] = true;
                }
                grid[i][j] = str.charAt(j);
            }
        }
        for (int i = 1; i < 2 * n; i++) {
            for (int j = 0; j < n; j++) {
                for (int j2 = 0; j2 < n; j2++) {
                    if(grid[j][j2] == 'G' || grid[j][j2] == 'M'){
                        times[i][j][j2] = mark(j, j2, times[i - 1]);
                    }
                }
            }
        }
        for (int i = 0; i < 2 * n; i++) {
            Queue<int[]> cur = new LinkedList<>();
            cur.add(new int[]{start[0], start[1], 0});
            boolean[][] visited = new boolean[n][n]; 
            visited[start[0]][start[1]] = true;
            for (int j = i; j < 2 * n; j++) {
                while(!cur.isEmpty() && Math.ceil(cur.peek()[2]/s) == j - i){
                    int[] x = cur.poll();
                    if(times[j][x[0]][x[1]]){
                        continue;
                    }
                    for (int k = 0; k < 4; k++) {
                        int fx = x[0] + dx[k];
                        int fy = x[1] + dy[k];
                        if(check(fx, fy) && !times[j][fx][fy] && !visited[fx][fy] && grid[fx][fy] != 'T'){
                            visited[fx][fy] = true;
                            cur.add(new int[]{fx, fy, x[2] + 1});
                        }
                    }
                }
            }
            if(visited[end[0]][end[1]]){
                ans = i;
            }
        }
        pw.println(ans);
        pw.close();
    }
}

Subtask #1
23.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 8356 KB Output is correct
2 Correct 49 ms 8528 KB Output is correct
3 Correct 47 ms 8404 KB Output is correct
4 Correct 48 ms 8316 KB Output is correct
5 Correct 49 ms 8372 KB Output is correct
6 Correct 48 ms 8484 KB Output is correct
7 Runtime error 107 ms 65536 KB Execution killed with signal 9
8 Correct 59 ms 9012 KB Output is correct
9 Correct 57 ms 8800 KB Output is correct
10 Correct 56 ms 8592 KB Output is correct
11 Correct 55 ms 8688 KB Output is correct
12 Incorrect 102 ms 14520 KB Output isn't correct
13 Correct 87 ms 11824 KB Output is correct
14 Correct 122 ms 14296 KB Output is correct
15 Incorrect 91 ms 10840 KB Output isn't correct
16 Incorrect 93 ms 11928 KB Output isn't correct
17 Incorrect 91 ms 12012 KB Output isn't correct
18 Incorrect 100 ms 12392 KB Output isn't correct
19 Incorrect 97 ms 12108 KB Output isn't correct
20 Incorrect 125 ms 13132 KB Output isn't correct
21 Incorrect 112 ms 12456 KB Output isn't correct
22 Incorrect 108 ms 13524 KB Output isn't correct
23 Incorrect 106 ms 14020 KB Output isn't correct
24 Incorrect 128 ms 14312 KB Output isn't correct
25 Incorrect 105 ms 14288 KB Output isn't correct
26 Incorrect 130 ms 14772 KB Output isn't correct
27 Incorrect 126 ms 14452 KB Output isn't correct
28 Incorrect 155 ms 15016 KB Output isn't correct
29 Incorrect 116 ms 14632 KB Output isn't correct
30 Incorrect 146 ms 15000 KB Output isn't correct
31 Incorrect 133 ms 15164 KB Output isn't correct
32 Incorrect 149 ms 15368 KB Output isn't correct
33 Runtime error 103 ms 65536 KB Execution killed with signal 9
34 Runtime error 114 ms 65536 KB Execution killed with signal 9
35 Runtime error 112 ms 65536 KB Execution killed with signal 9
36 Runtime error 101 ms 65536 KB Execution killed with signal 9
37 Runtime error 106 ms 65536 KB Execution killed with signal 9
38 Runtime error 109 ms 65536 KB Execution killed with signal 9
39 Runtime error 106 ms 65536 KB Execution killed with signal 9
40 Runtime error 121 ms 65536 KB Execution killed with signal 9
41 Runtime error 105 ms 65536 KB Execution killed with signal 9
42 Runtime error 104 ms 65536 KB Execution killed with signal 9
43 Runtime error 111 ms 65536 KB Execution killed with signal 9
44 Runtime error 107 ms 65536 KB Execution killed with signal 9
45 Runtime error 97 ms 65536 KB Execution killed with signal 9
46 Runtime error 105 ms 65536 KB Execution killed with signal 9
47 Runtime error 109 ms 65536 KB Execution killed with signal 9
48 Runtime error 102 ms 65536 KB Execution killed with signal 9
49 Runtime error 103 ms 65536 KB Execution killed with signal 9
50 Runtime error 100 ms 65536 KB Execution killed with signal 9
51 Runtime error 105 ms 65536 KB Execution killed with signal 9
52 Runtime error 114 ms 65536 KB Execution killed with signal 9
53 Runtime error 106 ms 65536 KB Execution killed with signal 9
54 Runtime error 99 ms 65536 KB Execution killed with signal 9
55 Runtime error 111 ms 65536 KB Execution killed with signal 9
56 Runtime error 98 ms 65536 KB Execution killed with signal 9
57 Runtime error 95 ms 65536 KB Execution killed with signal 9
58 Runtime error 112 ms 65536 KB Execution killed with signal 9
59 Runtime error 98 ms 65536 KB Execution killed with signal 9
60 Runtime error 107 ms 65536 KB Execution killed with signal 9
61 Runtime error 111 ms 65536 KB Execution killed with signal 9
62 Runtime error 99 ms 65536 KB Execution killed with signal 9
63 Runtime error 100 ms 65536 KB Execution killed with signal 9
64 Runtime error 98 ms 65536 KB Execution killed with signal 9
65 Runtime error 102 ms 65536 KB Execution killed with signal 9
66 Runtime error 115 ms 65536 KB Execution killed with signal 9
67 Runtime error 97 ms 65536 KB Execution killed with signal 9
68 Runtime error 105 ms 65536 KB Execution killed with signal 9
69 Runtime error 106 ms 65536 KB Execution killed with signal 9
70 Runtime error 105 ms 65536 KB Execution killed with signal 9
71 Runtime error 111 ms 65536 KB Execution killed with signal 9
72 Runtime error 108 ms 65536 KB Execution killed with signal 9
73 Runtime error 105 ms 65536 KB Execution killed with signal 9
74 Runtime error 103 ms 65536 KB Execution killed with signal 9
75 Runtime error 105 ms 65536 KB Execution killed with signal 9
76 Runtime error 101 ms 65536 KB Execution killed with signal 9
77 Runtime error 98 ms 65536 KB Execution killed with signal 9
78 Runtime error 107 ms 65536 KB Execution killed with signal 9
79 Runtime error 106 ms 65536 KB Execution killed with signal 9
80 Runtime error 103 ms 65536 KB Execution killed with signal 9
81 Runtime error 99 ms 65536 KB Execution killed with signal 9
82 Runtime error 97 ms 65536 KB Execution killed with signal 9
83 Runtime error 110 ms 65536 KB Execution killed with signal 9
84 Runtime error 117 ms 65536 KB Execution killed with signal 9
85 Runtime error 99 ms 65536 KB Execution killed with signal 9
86 Runtime error 114 ms 65536 KB Execution killed with signal 9
87 Runtime error 107 ms 65536 KB Execution killed with signal 9
88 Runtime error 103 ms 65536 KB Execution killed with signal 9
89 Runtime error 95 ms 65536 KB Execution killed with signal 9
90 Runtime error 101 ms 65536 KB Execution killed with signal 9
91 Runtime error 103 ms 65536 KB Execution killed with signal 9
92 Runtime error 101 ms 65536 KB Execution killed with signal 9