제출 #325573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
325573		anishrajeev	Mecho (IOI09_mecho)	Java	33 / 100	1108 ms	65536 KiB

mecho

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

public class mecho {
    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());
        String[][] grid = new String[N][N];
        LinkedList<pair> list = new LinkedList<>();
        int[][] bees = new int[N][N];
        int startx = 0, starty = 0, homex = 0, homey = 0;
        for(int i = 0; i < N; i++){
            String line = bf.readLine();
            String[] str = line.split("");
            Arrays.fill(bees[i], Integer.MAX_VALUE);
            for(int c = 0; c < N; c++){
                grid[i][c] = str[c];
                if(grid[i][c].equals("H")){
                    list.add(new pair(i, c, 0));
                    bees[i][c] = 0;
                }
                if(grid[i][c].equals("M")){
                    startx = i;
                    starty = c;
                }
                if(grid[i][c].equals("D")){
                    homex = i;
                    homey = c;
                }
            }
        }
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        boolean[][] visited = new boolean[N][N];
        while(!list.isEmpty()){
            pair p = list.pop();
            if(p.x == homex && p.y == homey)continue;
            if(grid[p.x][p.y].equals("T"))continue;
            bees[p.x][p.y] = Math.min(bees[p.x][p.y], p.t+S);
            if(visited[p.x][p.y])continue;
            visited[p.x][p.y] = true;
            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;
                list.add(new pair(nx, ny, bees[p.x][p.y]));
            }
        }
        bees[homex][homey] = Integer.MAX_VALUE;
        int start = 0, end = 10000000;
        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;
        }
        System.out.println(start);
    }
    public static boolean verify(int[][] bees, String[][] grid, int time, int startx, int starty, int homex, int homey, int N, int S){
        Stack<pair> stack = new Stack<>();
        stack.push(new pair(startx, starty, time*S));
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        TreeSet<pair> visited = new TreeSet<>();
        while(!stack.isEmpty()){
            pair p = stack.pop();
            if(p.t >= bees[p.x][p.y])continue;
            if(visited.contains(p))continue;
            visited.add(p);
            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(bees[nx][ny] <= p.t)continue;
                if(grid[nx][ny].equals("T")||grid[nx][ny].equals("H"))continue;
                if(bees[nx][ny] <= p.t+1)continue;
                stack.push(new pair(nx, ny, p.t+1));
            }
        }
        stack = null;
        dx = null;
        dy = null;
        for(pair p:visited){
            if(p.x == homex && p.y == homey){
                visited = null;
                return true;
            }
        }
        return false;
    }
    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: 33 / 100