제출 #815903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
815903		powervic08	Mecho (IOI09_mecho)	Java	95 / 100	551 ms	51344 KiB

mecho

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

public class mecho {

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int S;

    public static void main(String[] args) throws IOException {
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        int[][] grid = new int[n][n];
        int starti = 0, startj = 0, endi = 0, endj = 0;
        for (int i = 0; i < n; i++) {
            String s = f.readLine();
            for (int j = 0; j < n; j++) {
                if (s.charAt(j) == 'H') grid[i][j] = 1;
                else if (s.charAt(j) == 'T') grid[i][j] = 2;
                else if (s.charAt(j) == 'M') {
                    starti = i;
                    startj = j;
                } else if (s.charAt(j) == 'D') {
                    endi = i;
                    endj = j;
                }
            }
        }
        out.println(maximumMinutes(grid, starti, startj, endi, endj));
        out.close();
        f.close();
    }

    public static int maximumMinutes(int[][] grid, int starti, int startj, int endi, int endj) {
        int n = grid.length;
        int m = grid[0].length;
        Queue<Node> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    q.add(new Node(i, j, 0));
                }
            }
        }
        long[][] dists = new long[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dists[i], Long.MAX_VALUE);
        }
        while (!q.isEmpty()) {
            Node p = q.poll();
            if (p.dist >= dists[p.i][p.j]) {
                continue;
            }
            dists[p.i][p.j] = p.dist;
            for (int i = 0; i < 4; i++) {
                int newi = dx[i] + p.i;
                int newj = dy[i] + p.j;
                if (inRange(newi, newj, grid)) {
                    if (grid[newi][newj] != 2) {
                        q.add(new Node(newi, newj, p.dist + S));
                    }
                }
            }
        }
        dists[endi][endj] = Integer.MAX_VALUE;
        int l = -1;
        int r = 2 * n * n;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (works(mid, dists, grid, starti, startj, endi, endj)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l;
    }

    public static boolean works(int mid, long[][] dists, int[][] grid, int starti, int startj, int endi, int endj) {
        Queue<Node> q = new LinkedList<>();
        if ((long) mid * S >= dists[starti][startj])
            return false;
        q.add(new Node(starti, startj, (long) mid * S));
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        while (!q.isEmpty()) {
            Node p = q.poll();
            if (p.i == endi && p.j == endj) {
                return true;
            }
            if (visited[p.i][p.j]) {
                continue;
            }
            visited[p.i][p.j] = true;
            for (int i = 0; i < 4; i++) {
                int newi = dx[i] + p.i;
                int newj = dy[i] + p.j;
                if (inRange(newi, newj, grid)) {
                    if (grid[newi][newj] == 0 && dists[newi][newj] > p.dist + 1 && !visited[newi][newj]) {
                        q.add(new Node(newi, newj, p.dist + 1));
                    }
                }
            }
        }
        return false;
    }

    public static boolean inRange(int i, int j, int[][] grid) {
        return i >= 0 && j >= 0 && i < grid.length && j < grid[0].length;
    }

    static class Node {
        int i, j;
        long dist;

        public Node(int a, int b, long c) {
            i = a;
            j = b;
            dist = c;
        }
    }

}

• Subtask 1: 95 / 100