답안 #328220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
328220	2020-11-15T21:36:23 Z	anishrajeev	Mecho (IOI09_mecho)	Java 11	46 / 100	1000 ms	25256 KB

mecho

import java.io.*;
import java.util.*;

public class mecho {
    public static LinkedList<pair> q = new LinkedList<>();
    public static int[] dx = new int[]{0, 1, 0, -1};
    public static int[] dy = new int[]{1, 0, -1, 0};
    public static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader bf = new BufferedReader(new FileReader("tester.in"));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(stk.nextToken());
        int S = Integer.parseInt(stk.nextToken());
        char[][] grid = new char[N][N];
        int[][] bees = new int[N][N];
        visited = new boolean[N][N];
        int startx = 0, starty = 0, homex = 0, homey = 0;
        for(int i = 0; i < N; i++){
            String line = bf.readLine();
            Arrays.fill(bees[i], Integer.MAX_VALUE);
            for(int c = 0; c < N; c++){
                grid[i][c] = line.charAt(c);
                if(grid[i][c] == 'H'){
                    q.add(new pair(i, c, 0));
                    visited[i][c] = true;
                    bees[i][c] = 0;
                }
                if(grid[i][c] == 'M'){
                    startx = i;
                    starty = c;
                }
                if(grid[i][c]=='D'){
                    homex = i;
                    homey = c;
                }
            }
        }
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        while(!q.isEmpty()){
            pair p = q.pop();
            if(p.x == homex && p.y == homey)continue;
            if(grid[p.x][p.y] == 'T')continue;
            bees[p.x][p.y] = Math.min(bees[p.x][p.y], p.t+S);
            for(int i = 0; i < 4; i++){
                int nx = p.x+dx[i];
                int ny = p.y+dy[i];
                if(N <= nx || nx < 0 || N <= ny || ny < 0 || visited[nx][ny])continue;
                q.add(new pair(nx, ny, bees[p.x][p.y]));
                visited[nx][ny] = true;

            }
        }
        bees[homex][homey] = Integer.MAX_VALUE;
        int start = 0, end = 100000000;
        while(start != end){
            int mid = (start+end+1)/2;
            if(verify(bees, grid, mid, startx, starty, homex, homey, N, S))start = mid;
            else end = mid-1;
        }
        if(!verify(bees, grid, 0, startx, starty, homex, homey, N, S))System.out.println(-1);
        else System.out.println(start);
    }
    public static boolean verify(int[][] bees, char[][] grid, int time, int startx, int starty, int homex, int homey, int N, int S){
        q.add(new pair(startx, starty, time*S));
        for(int i = 0; i < N; i++)Arrays.fill(visited[i], false);
        visited[startx][starty] = true;
        while(!q.isEmpty()){
            pair p = q.poll();
            if(p.t >= bees[p.x][p.y])continue;
            for(int i = 0; i < 4; i++){
                int nx = p.x+dx[i];
                int ny = p.y+dy[i];
                if(N <= nx || nx < 0 || N <= ny || ny < 0)continue;
                if(grid[nx][ny]=='T'||grid[nx][ny]=='H')continue;
                if(bees[nx][ny] <= p.t+1 || visited[nx][ny])continue;
                q.add(new pair(nx, ny, p.t+1));
                visited[nx][ny] = true;
            }
        }
        return visited[homex][homey];
    }
    public static class pair implements Comparable<pair>{
        int x, y, t;
        public pair(int a, int b, int c){
            x = a;
            y = b;
            t = c;
        }

        @Override
        public int compareTo(pair o) {
            if(x==o.x&&y==o.y)return Integer.compare(t, o.t);
            if(x==o.x)return Integer.compare(y, o.y);
            return Integer.compare(x, o.x);
        }
        public boolean equals(pair o){
            if(x == o.x && y == o.y && t == o.t)return true;
            return false;
        }
    }
}

Subtask #1

46.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	71 ms	8428 KB	Output is correct
2	Correct	71 ms	8684 KB	Output is correct
3	Correct	70 ms	8556 KB	Output is correct
4	Correct	73 ms	8664 KB	Output is correct
5	Correct	73 ms	8556 KB	Output is correct
6	Correct	72 ms	8556 KB	Output is correct
7	Execution timed out	1093 ms	22360 KB	Time limit exceeded
8	Correct	72 ms	8556 KB	Output is correct
9	Correct	74 ms	8556 KB	Output is correct
10	Correct	73 ms	8428 KB	Output is correct
11	Correct	72 ms	8556 KB	Output is correct
12	Correct	85 ms	8808 KB	Output is correct
13	Correct	82 ms	8812 KB	Output is correct
14	Correct	142 ms	11904 KB	Output is correct
15	Correct	77 ms	8528 KB	Output is correct
16	Correct	78 ms	8684 KB	Output is correct
17	Correct	78 ms	8684 KB	Output is correct
18	Correct	78 ms	8812 KB	Output is correct
19	Correct	79 ms	8684 KB	Output is correct
20	Correct	78 ms	8684 KB	Output is correct
21	Correct	80 ms	8684 KB	Output is correct
22	Correct	82 ms	8704 KB	Output is correct
23	Correct	89 ms	9088 KB	Output is correct
24	Correct	89 ms	8812 KB	Output is correct
25	Correct	88 ms	8940 KB	Output is correct
26	Correct	94 ms	8940 KB	Output is correct
27	Correct	94 ms	8940 KB	Output is correct
28	Correct	118 ms	10976 KB	Output is correct
29	Correct	98 ms	8940 KB	Output is correct
30	Correct	125 ms	12024 KB	Output is correct
31	Correct	148 ms	12156 KB	Output is correct
32	Correct	155 ms	12340 KB	Output is correct
33	Correct	302 ms	15412 KB	Output is correct
34	Incorrect	437 ms	15416 KB	Output isn't correct
35	Incorrect	572 ms	15432 KB	Output isn't correct
36	Correct	328 ms	16136 KB	Output is correct
37	Incorrect	451 ms	15544 KB	Output isn't correct
38	Incorrect	663 ms	15664 KB	Output isn't correct
39	Correct	301 ms	16180 KB	Output is correct
40	Incorrect	490 ms	15904 KB	Output isn't correct
41	Incorrect	666 ms	16200 KB	Output isn't correct
42	Correct	323 ms	16676 KB	Output is correct
43	Incorrect	569 ms	16428 KB	Output isn't correct
44	Incorrect	734 ms	16548 KB	Output isn't correct
45	Correct	339 ms	16956 KB	Output is correct
46	Incorrect	560 ms	16840 KB	Output isn't correct
47	Incorrect	881 ms	17104 KB	Output isn't correct
48	Correct	353 ms	17556 KB	Output is correct
49	Incorrect	497 ms	17348 KB	Output isn't correct
50	Incorrect	833 ms	17236 KB	Output isn't correct
51	Correct	333 ms	17996 KB	Output is correct
52	Incorrect	549 ms	17720 KB	Output isn't correct
53	Incorrect	998 ms	17684 KB	Output isn't correct
54	Correct	343 ms	18340 KB	Output is correct
55	Incorrect	571 ms	18232 KB	Output isn't correct
56	Execution timed out	1056 ms	18120 KB	Time limit exceeded
57	Correct	355 ms	18988 KB	Output is correct
58	Incorrect	567 ms	18616 KB	Output isn't correct
59	Execution timed out	1042 ms	19016 KB	Time limit exceeded
60	Correct	385 ms	19404 KB	Output is correct
61	Incorrect	644 ms	19016 KB	Output isn't correct
62	Execution timed out	1092 ms	19144 KB	Time limit exceeded
63	Correct	508 ms	19220 KB	Output is correct
64	Execution timed out	1090 ms	19304 KB	Time limit exceeded
65	Correct	644 ms	19348 KB	Output is correct
66	Correct	589 ms	19056 KB	Output is correct
67	Correct	549 ms	19348 KB	Output is correct
68	Correct	444 ms	19508 KB	Output is correct
69	Execution timed out	1039 ms	19348 KB	Time limit exceeded
70	Correct	425 ms	19528 KB	Output is correct
71	Correct	425 ms	19480 KB	Output is correct
72	Incorrect	880 ms	19584 KB	Output isn't correct
73	Correct	426 ms	25052 KB	Output is correct
74	Execution timed out	1068 ms	24852 KB	Time limit exceeded
75	Correct	544 ms	25256 KB	Output is correct
76	Correct	513 ms	24980 KB	Output is correct
77	Correct	538 ms	25000 KB	Output is correct
78	Correct	594 ms	25032 KB	Output is correct
79	Execution timed out	1086 ms	25100 KB	Time limit exceeded
80	Correct	613 ms	25000 KB	Output is correct
81	Correct	593 ms	24760 KB	Output is correct
82	Correct	554 ms	24932 KB	Output is correct
83	Correct	593 ms	23892 KB	Output is correct
84	Execution timed out	1100 ms	24076 KB	Time limit exceeded
85	Correct	619 ms	24000 KB	Output is correct
86	Correct	559 ms	23920 KB	Output is correct
87	Execution timed out	1098 ms	24000 KB	Time limit exceeded
88	Correct	601 ms	23276 KB	Output is correct
89	Execution timed out	1100 ms	23104 KB	Time limit exceeded
90	Execution timed out	1052 ms	23280 KB	Time limit exceeded
91	Execution timed out	1090 ms	22932 KB	Time limit exceeded
92	Correct	597 ms	23204 KB	Output is correct