제출 #794962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
794962		sushikid	Mecho (IOI09_mecho)	Java	53 / 100	391 ms	26804 KiB

mecho

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, s;
    private static char[][] grid;
    private static int[][] bees;
    private static int[] start, end;

    private static boolean valid(int x, int y){
        return 0 <= x && x < n && 0 <= y && y < n;
    }
    private static boolean check(int x){
        if(bees[start[0]][start[1]] <= x){
            return false;
        }

        boolean[][] dist = new boolean[n][n];
        Queue<int[]> cur = new LinkedList<>();
        cur.add(new int[]{start[0], start[1], 0});

        dist[start[0]][start[1]] = true;
        while(!cur.isEmpty()){
            int[] z = cur.poll();
            for (int i = 0; i < 4; i++) {
                int fx = z[0] + dx[i];
                int fy = z[1] + dy[i];
                if(valid(fx, fy) && !dist[fx][fy] && grid[fx][fy] != 'T' && (z[2] + 1)/s + x < bees[fx][fy]){
                    dist[fx][fy] = true;
                    cur.add(new int[]{fx, fy, z[2] + 1});
                }
            }
        }
        return dist[end[0]][end[1]];
    }
    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()); s = Integer.parseInt(st.nextToken());

        grid = new char[n][n];
        start = new int[]{-1, -1}; end = new int[]{-1, -1};
        Queue<int[]> hives = new LinkedList<>();
        bees = new int[n][n];

        for (int i = 0; i < n; i++) {
            Arrays.fill(bees[i], Integer.MAX_VALUE);
        }
        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});
                    bees[i][j] = 0;
                }
                grid[i][j] = str.charAt(j);
            }
        }
        while(!hives.isEmpty()){
            int[] x = hives.poll();
            for (int i = 0; i < 4; i++) {
                int fx = x[0] + dx[i];
                int fy = x[1] + dy[i];
                if(valid(fx, fy) && bees[fx][fy] == Integer.MAX_VALUE && (grid[fx][fy] == 'G' || grid[fx][fy] == 'M')){
                    bees[fx][fy] = x[2] + 1;
                    hives.add(new int[]{fx, fy, x[2] + 1});
                }
            }
        }
        int left = 0;
        int right = 2 * n;
        while(left < right){
            int mid = left + (right - left + 1)/2;
            if(check(mid)){
                left = mid;
            }
            else{
                right = mid - 1;
            }
        }
        if(check(right)){
            pw.println(right);
        }
        else{
            pw.println(-1);
        }
        pw.close();
    }
}

• Subtask 1: 53 / 100