답안 #328222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
328222	2020-11-15T21:47:44 Z	anishrajeev	Mecho (IOI09_mecho)	Java 11	100 / 100	848 ms	25068 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 = 1000000;
        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

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	70 ms	8556 KB	Output is correct
2	Correct	71 ms	8412 KB	Output is correct
3	Correct	74 ms	8660 KB	Output is correct
4	Correct	72 ms	8684 KB	Output is correct
5	Correct	72 ms	8556 KB	Output is correct
6	Correct	71 ms	8556 KB	Output is correct
7	Correct	749 ms	22720 KB	Output is correct
8	Correct	72 ms	8556 KB	Output is correct
9	Correct	72 ms	8556 KB	Output is correct
10	Correct	74 ms	8684 KB	Output is correct
11	Correct	73 ms	8556 KB	Output is correct
12	Correct	83 ms	8812 KB	Output is correct
13	Correct	83 ms	8812 KB	Output is correct
14	Correct	164 ms	12172 KB	Output is correct
15	Correct	74 ms	8556 KB	Output is correct
16	Correct	74 ms	8556 KB	Output is correct
17	Correct	76 ms	8684 KB	Output is correct
18	Correct	77 ms	8684 KB	Output is correct
19	Correct	81 ms	8664 KB	Output is correct
20	Correct	78 ms	8684 KB	Output is correct
21	Correct	80 ms	8684 KB	Output is correct
22	Correct	81 ms	8812 KB	Output is correct
23	Correct	83 ms	8684 KB	Output is correct
24	Correct	88 ms	8940 KB	Output is correct
25	Correct	88 ms	8940 KB	Output is correct
26	Correct	121 ms	11768 KB	Output is correct
27	Correct	89 ms	8940 KB	Output is correct
28	Correct	95 ms	8784 KB	Output is correct
29	Correct	95 ms	8940 KB	Output is correct
30	Correct	115 ms	10824 KB	Output is correct
31	Correct	115 ms	10800 KB	Output is correct
32	Correct	132 ms	12100 KB	Output is correct
33	Correct	341 ms	15328 KB	Output is correct
34	Correct	392 ms	15288 KB	Output is correct
35	Correct	409 ms	15440 KB	Output is correct
36	Correct	343 ms	15580 KB	Output is correct
37	Correct	392 ms	15560 KB	Output is correct
38	Correct	433 ms	15840 KB	Output is correct
39	Correct	353 ms	15968 KB	Output is correct
40	Correct	406 ms	15944 KB	Output is correct
41	Correct	471 ms	16056 KB	Output is correct
42	Correct	369 ms	16512 KB	Output is correct
43	Correct	445 ms	16440 KB	Output is correct
44	Correct	506 ms	16644 KB	Output is correct
45	Correct	361 ms	17008 KB	Output is correct
46	Correct	428 ms	16824 KB	Output is correct
47	Correct	580 ms	17012 KB	Output is correct
48	Correct	364 ms	17248 KB	Output is correct
49	Correct	432 ms	17352 KB	Output is correct
50	Correct	589 ms	17364 KB	Output is correct
51	Correct	371 ms	17900 KB	Output is correct
52	Correct	435 ms	17736 KB	Output is correct
53	Correct	631 ms	17876 KB	Output is correct
54	Correct	381 ms	18280 KB	Output is correct
55	Correct	441 ms	17992 KB	Output is correct
56	Correct	696 ms	18388 KB	Output is correct
57	Correct	384 ms	18644 KB	Output is correct
58	Correct	446 ms	18616 KB	Output is correct
59	Correct	759 ms	18808 KB	Output is correct
60	Correct	413 ms	19272 KB	Output is correct
61	Correct	455 ms	19200 KB	Output is correct
62	Correct	825 ms	19528 KB	Output is correct
63	Correct	686 ms	19308 KB	Output is correct
64	Correct	820 ms	19432 KB	Output is correct
65	Correct	848 ms	19432 KB	Output is correct
66	Correct	779 ms	19560 KB	Output is correct
67	Correct	728 ms	19404 KB	Output is correct
68	Correct	535 ms	19476 KB	Output is correct
69	Correct	526 ms	19468 KB	Output is correct
70	Correct	506 ms	19552 KB	Output is correct
71	Correct	483 ms	19508 KB	Output is correct
72	Correct	505 ms	19380 KB	Output is correct
73	Correct	426 ms	24980 KB	Output is correct
74	Correct	702 ms	24968 KB	Output is correct
75	Correct	653 ms	25060 KB	Output is correct
76	Correct	650 ms	24840 KB	Output is correct
77	Correct	684 ms	25068 KB	Output is correct
78	Correct	643 ms	25028 KB	Output is correct
79	Correct	717 ms	24792 KB	Output is correct
80	Correct	697 ms	24924 KB	Output is correct
81	Correct	694 ms	24736 KB	Output is correct
82	Correct	688 ms	24800 KB	Output is correct
83	Correct	685 ms	24004 KB	Output is correct
84	Correct	695 ms	23928 KB	Output is correct
85	Correct	703 ms	24280 KB	Output is correct
86	Correct	666 ms	24132 KB	Output is correct
87	Correct	719 ms	24028 KB	Output is correct
88	Correct	640 ms	22976 KB	Output is correct
89	Correct	787 ms	23104 KB	Output is correct
90	Correct	729 ms	23344 KB	Output is correct
91	Correct	749 ms	23268 KB	Output is correct
92	Correct	717 ms	23360 KB	Output is correct