Submission #527645

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

mecho

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Mecho {
    static int[] xBfs = {1, -1, 0, 0};
    static int[] yBfs = {0, 0, 1, -1};
    static int n;
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    int s = sc.nextInt();

    char[][] grid = new char[n][n];

    int[][] beeDistance = new int[n][n];
    boolean[][] beeVisited = new boolean[n][n];
    Queue<Coordinate> q = new LinkedList<>();
    Coordinate mecho = new Coordinate(-1, -1);
        for (int i = 0; i < n; i++) {
            String temp = sc.next();
            for (int j = 0; j < n; j++) {
                grid[i][j] = temp.charAt(j);
                if(grid[i][j] == 'M') {
                    mecho = new Coordinate(i, j);
                }
                else if(grid[i][j] == 'H') {//its a hive
                    q.add(new Coordinate(i, j));
                    beeDistance[i][j] = 0;
                    beeVisited[i][j] = true;
                }
            }
        }

        beeBFS(grid, beeDistance, beeVisited, q); //run bfs on bees

        q = new LinkedList<>(); //mecho bfs preparation
        q.add(new Coordinate(mecho.x, mecho.y));
        int[][] mechoDistance = new int[n][n];
        boolean[][] mechoVisited = new boolean[n][n];
        mechoVisited[mecho.x][mecho.y] = true;
        Coordinate[][] previousLocation = new Coordinate[n][n];
        previousLocation[mecho.x][mecho.y] = new Coordinate(-1, -1);

        mechoBFS(mechoDistance, mechoVisited, previousLocation, q, grid, beeDistance, beeVisited, s);        //mecho bfs
    }
    private static void mechoBFS(int[][] mechoDistance, boolean[][] mechoVisited,
                                 Coordinate[][] previousLocation, Queue<Coordinate> q, char[][] grid, int[][] beeDistance, boolean[][] beeVisited, int s) {
        //I need to actually write and not copy this part.
        boolean endThis = false;
        while(!q.isEmpty() && !endThis) {
            Coordinate c = q.poll();
            int x = c.x;
            int y = c.y;
            for (int i = 0; i < 4; i++) {
                int curX = x + xBfs[i];
                int curY = y + yBfs[i];
                if(onGrid(curX, curY) && !mechoVisited[curX][curY] && grid[curX][curY] != 'T') {
                    if(beeVisited[curX][curY] && ((mechoDistance[x][y] + 1) / s) < beeDistance[curX][curY]) {
                        mechoVisited[curX][curY] = true;
                        mechoDistance[curX][curY] = mechoDistance[x][y] + 1;
                        q.add(new Coordinate(curX, curY));
                        previousLocation[curX][curY] = new Coordinate(x, y);
                    }
                }

                if(onGrid(curX, curY) && grid[curX][curY] == 'D') { //we found the shortest path.
                        //all other paths from this point onwards is irrelevant.
                    findAnswer(mechoDistance, previousLocation, grid, beeDistance, s, new Coordinate(curX, curY));
                    endThis = true;
                }
                if(endThis) break;
            }
        }
    }

    private static void findAnswer(
            int[][] mechoDistance, Coordinate[][] previousLocation, char[][] grid,
            int[][] beeDistance, int mechoSpeed, Coordinate home) {
        //check if the current position is possible,
        //bees expand one position
        int waitTime = 0;
        boolean impossible = false;
        while(true) {
            Coordinate current = new Coordinate(home.x, home.y);
            while(current.x != -1 && current.y != -1) { //-1, -1 is the original honeypot
                if((mechoDistance[current.x][current.y] / mechoSpeed)
                        < (beeDistance[current.x][current.y] - waitTime)) {
                    int x = current.x;
                    int y = current.y;
                    current.x = previousLocation[x][y].x;
                    current.y = previousLocation[x][y].y;
                }

                else {
                    impossible = true;
                    break;
                }
            }
            if(impossible) break;
            waitTime++;
        }
        System.out.println(waitTime); //remember to implement -1...
    }

    private static void beeBFS(char[][] grid, int[][] beeDistance,
                               boolean[][] beeVisited, Queue<Coordinate> q) {
        while(!q.isEmpty()) {
            Coordinate c = q.poll();
            int x = c.x;
            int y = c.y;
            for (int i = 0; i < 4; i++) {
                int curX = x + xBfs[i];
                int curY = y + yBfs[i];
                if(onGrid(curX, curY) && !beeVisited[curX][curY] && grid[curX][curY] != 'T') {
                    beeVisited[curX][curY] = true;
                    beeDistance[curX][curY] = beeDistance[x][y] + 1;
                    q.add(new Coordinate(curX, curY));
                }
            }
        }
    }
    public static boolean onGrid(int x, int y) {
        return (x >= 0 && x < n && y >= 0 && y < n);
    }}
class Coordinate {
    int x, y;
    public Coordinate(int x, int y) {this. x = x; this.y = y;}
}

Compilation message (stderr)

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