제출 #581665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581665		DylanSmith	Mecho (IOI09_mecho)	Java	31 / 100	641 ms	30920 KiB

mecho

import java.util.*;
import java.io.*;
public class mecho {
    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        PrintWriter out = new PrintWriter(System.out);
        
        int N = in.nextInt(), K = in.nextInt();
        char[][] mat = new char[N][N];
        for (int i = 0; i < N; i++) {
            mat[i] = in.next().toCharArray();
        }
        Queue<int[]> q = new LinkedList<>();
        int[][] bee = new int[N][N];
        int[] start = new int[2], end = new int[2];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (mat[i][j] == 'H') {
                    bee[i][j] = 0;
                    q.offer(new int[]{i, j});
                } else {
                    bee[i][j] = -1;
                }
                if (mat[i][j] == 'M') {
                    start = new int[]{i, j};
                }
                if (mat[i][j] == 'D') {
                    end = new int[]{i, j};
                }
            }
        }
        int[] x = new int[]{-1, 1, 0, 0}, y = new int[]{0, 0, -1, 1};
        while (!q.isEmpty()) {
            int[] current = q.poll();
            int r = current[0], c = current[1];
            for (int k = 0; k < 4; k++) {
                int r2 = r + x[k], c2 = c + y[k];
                if (r2 >= 0 && r2 < N && c2 >= 0 && c2 < N) {
                    if (mat[r2][c2] != 'D' && bee[r2][c2] == -1) {
                        bee[r2][c2] = bee[r][c] + 1;
                        q.offer(new int[]{r2, c2});
                    }
                }
            }
        }
        out.println(search(mat, bee, start, end, K, 0, N * N));
        
        out.close();
    }
    public static int search(char[][] mat, int[][] bee, int[] start, int[] end, int K, int l, int r) {
        if (l > r) {
            return -1;
        }
        int mid = (l + r) / 2;
        if (check(mat, bee, start, end, K, mid)) {
            int m = search(mat, bee, start, end, K, mid + 1, r);
            if (m == -1) {
                return mid;
            }
            return m;
        }
        return search(mat, bee, start, end, K, l, mid - 1);
    }
    public static boolean check(char[][] mat, int[][] bee, int[] start, int[] end, int K, int eat) {
        int N = mat.length;
        int[][] dist = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(dist[i], -1);
        }
        dist[start[0]][start[1]] = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(start);
        int[] x = new int[]{-1, 1, 0, 0}, y = new int[]{0, 0, -1, 1};
        while (!q.isEmpty()) {
            int[] current = q.poll();
            int r = current[0], c = current[1];
            for (int k = 0; k < 4; k++) {
                int r2 = r + x[k], c2 = c + y[k];
                if (r2 >= 0 && r2 < N && c2 >= 0 && c2 < N) {
                    if (mat[r2][c2] != 'T' && mat[r2][c2] != 'H' && dist[r2][c2] == -1) {
                        if (mat[r2][c2] == 'D' || (dist[r][c] + 1) / K + eat < bee[r2][c2]) {
                            dist[r2][c2] = dist[r][c] + 1;
                            q.offer(new int[]{r2, c2});
                        }
                    }
                }
            }
        }
        return dist[end[0]][end[1]] >= 0;
    }
    static class Reader {
        BufferedInputStream in;
        public Reader() {
            in = new BufferedInputStream(System.in);
        }
        public String nextLine() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public String next() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != ' ' && c != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public int nextInt() throws IOException {
            return (int)nextLong();
        }
        public long nextLong() throws IOException {
            int c;
            long res = 0;
            boolean start = false, negative = false;
            while ((c = in.read()) != ' ' && c != '\n' || !start)
                if (c >= '0' && c <= '9' || c == '-') {
                    start = true;
                    if (c == '-')
                        negative = true;
                    else
                        res = res * 10 + c - '0';
                }
            return res * (negative ? -1 : 1);
        }
    }
    public static void sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        Collections.sort(list);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
    }
}

• Subtask 1: 31 / 100