제출 #794860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
794860		sushikid	Mecho (IOI09_mecho)	Java	3 / 100	168 ms	65536 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;
    private static char[][] grid;

    private static boolean mark(int x, int y, boolean[][] arr){
        for (int i = 0; i < 4; i++) {
            int fx = x + dx[i];
            int fy = y + dy[i];
            if(check(fx, fy) && arr[fx][fy] && grid[fx][fy] != 'T'){
                return true;
            }
        }
        return arr[x][y];
    }
    private static boolean check(int x, int y){
        return 0 <= x && x < n && 0 <= y && y < n;
    }
    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()); int s = Integer.parseInt(st.nextToken());

        grid = new char[n][n];
        int[] start = {-1, -1}; int[] end = {-1, -1};
        Queue<int[]> hives = new LinkedList<>();
        int ans = -1;
        boolean[][][] times = new boolean[2 * n][n][n];

        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});
                    times[0][i][j] = true;
                }
                grid[i][j] = str.charAt(j);
            }
        }
        for (int i = 1; i < 2 * n; i++) {
            for (int j = 0; j < n; j++) {
                for (int j2 = 0; j2 < n; j2++) {
                    if(grid[j][j2] == 'T'){
                        continue;
                    }
                    times[i][j][j2] = mark(j, j2, times[i - 1]);
                }
            }
        }
        for (int i = 0; i < 2 * n; i++) {
            Queue<int[]> cur = new LinkedList<>();
            cur.add(new int[]{start[0], start[1], 0});
            boolean[][] visited = new boolean[n][n]; 
            visited[start[0]][start[1]] = true;
            for (int j = i; j < 2 * n; j++) {
                while(!cur.isEmpty() && Math.ceil(cur.peek()[0]/s) <= j - i){
                    int[] x = cur.poll();
                    if(times[j][x[0]][x[1]]){
                        continue;
                    }
                    for (int k = 0; k < 4; k++) {
                        int fx = x[0] + dx[k];
                        int fy = x[1] + dy[k];
                        if(check(fx, fy) && !times[j][fx][fy] && !visited[fx][fy] && grid[fx][fy] != 'T'){
                            visited[fx][fy] = true;
                            cur.add(new int[]{fx, fy, x[2] + 1});
                        }
                    }
                }
            }
            // for(boolean[] e : visited){
            //     System.out.println(Arrays.toString(e));
            // }
            // System.out.println("===");
            if(visited[end[0]][end[1]]){
                ans = i;
            }
        }
        pw.println(ans);
        pw.close();
    }
}

• Subtask 1: 3 / 100