Submission #490563

#	Time	Username	Problem	Language	Result	Execution time	Memory
490563		vijay	Mecho (IOI09_mecho)	Java	Compilation error	0 ms	0 KiB

mecho

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

public class Main {
    static int N, S;
    static int[][] distFromHive;
    static int startX, startY, endX, endY;
    static int[] dX, dY;
    static boolean[][] forest;
    public static void main(String[] args) throws IOException, FileNotFoundException {
        Scanner in = new Scanner(System.in);
        // Scanner in = new Scanner(new File("test.in"));

        N = in.nextInt();
        S = in.nextInt();

        forest = new boolean[N][N];

        PriorityQueue<State> pq = new PriorityQueue<>();

        for(int i = 0; i < N; i++){
            String line = in.next();
            for(int j = 0; j < N; j++){
                int cchar = line.charAt(j);
                if(cchar == 'T'){
                    forest[i][j] = true;
                } else if (cchar == 'M'){
                    startX = i;
                    startY = j;
                } else if (cchar == 'D'){
                    endX = i;
                    endY = j;
                } else if (cchar == 'H'){
                    pq.add(new State(i, j, 0));
                }
            } 
        }

        distFromHive = new int[N][N];
        for(int i = 0; i < N; i++){
            Arrays.fill(distFromHive[i], -1);
        }

        dX = new int[] {-1, 1, 0, 0};
        dY = new int[] {0, 0, -1, 1};

        while(!pq.isEmpty()){
            State curr = pq.poll();
            if(distFromHive[curr.x][curr.y] != -1){
                continue;
            }
            distFromHive[curr.x][curr.y] = curr.dist;
            for(int i = 0; i < 4; i++){
                int nX = curr.x + dX[i];
                int nY = curr.y + dY[i];
                if(nX < 0 || nX >= N || nY < 0 || nY >= N || forest[nX][nY]){
                    continue;
                }
                pq.add(new State(nX, nY, curr.dist + 1));
            }
        }

        // for(int i = 0; i < N; i++){
        //     System.out.println(Arrays.toString(distFromHive[i]));
        // }

        int a = 0;
        int b = 1000000;
        while(a != b){
            int mid = (a + b + 1)/2;
            if(works(mid)){
                a = mid;
            } else {
                b = mid - 1;
            }
        }

        System.out.println(a);
    }

    public static boolean works(int wait){
        PriorityQueue<State> pq = new PriorityQueue<>();
        pq.add(new State(startX, startY, wait * S));
        boolean[][] visited = new boolean[N][N];
        while(!pq.isEmpty()){
            State curr = pq.poll();
            if(visited[curr.x][curr.y]){
                continue;
            }

            if(curr.x == endX && curr.y == endY){
                // System.out.println("get to " + curr.x + " " + curr.y + " in " + curr.dist + " vs. " + distFromHive[curr.x][curr.y]);
                return true;
            }

            if(distFromHive[curr.x][curr.y] * S <= curr.dist){
                continue;
            }

            for(int i = 0; i < 4; i++){
                int nX = curr.x + dX[i];
                int nY = curr.y + dY[i];
                if(nX < 0 || nX >= N || nY < 0 || nY >= N || forest[nX][nY]){
                    continue;
                }
                pq.add(new State(nX, nY, curr.dist + 1));
            }
        }
        return false;
    }

    public static class State implements Comparable<State>{
        int x, y, dist;
        public State(int x, int y, int dist){
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
        public int compareTo(State s){
            return dist - s.dist;
        }
    }
}

Compilation message (stderr)

mecho.java:4: error: class Main is public, should be declared in a file named Main.java
public class Main {
       ^
1 error