Submission #584746

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
584746	2022-06-28T01:26:28 Z	PikaChu999	Mecho (IOI09_mecho)	Java 11	Compilation error	0 ms	0 KB

mecho

/*
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT

1. Find shortest time it takes for the bees to reach every cell, and the shortest time it takes for Mecho to reach every cell (in minutes, take ceiling(steps it took for Mecho to get there (divided by) steps Mecho can take in a minute))
2. Binary search on the largest # of minutes that Mecho can eat honey for
*/
import java.util.*;
import java.io.*;

public class Main{
  public static int n; 
  public static long s; 
  public static char[][] grid; //'T' = tree, 'G' = grass, 'M' = mecho, 'H' = beehive, 'D' = mecho's house
  //Neither bees or mecho can enter the tree cells
  //Mecho can travel s steps in 1 minute --> can reach a certain cell in ceil(steps it took to get to that cell/s) minutes, bees travel every minute 
  //Given that Mecho waited for x minutes, Mecho can visit a cell iff mecho[x][y] + x < bee[x][y] 
  public static long max = 9;//1000000000; 
  public static int denx; 
  public static int deny; 
  public static int mechox; 
  public static int mechoy; 

  public static long[][] bees; 
  public static long[][] mecho; 

  public static int[] xc = {0,0,1,-1};
  public static int[] yc = {1,-1,0,0};
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer details = new StringTokenizer(br.readLine());
    n = Integer.parseInt(details.nextToken());
    s = Long.parseLong(details.nextToken());
    grid = new char[n][n]; 

    bees = new long[n][n]; //bees[a][b] = min # of minutes it takes for a bee to reach cell a,b
    for(long[] row : bees) Arrays.fill(row, max);
    mecho = new long[n][n]; //mecho[a][b] = before division, min # of steps it takes for mecho to reach cell a,b, after division min # of minutes (ceiling)
    for(long[] row : mecho) Arrays.fill(row, max);
    ArrayDeque<State> bq = new ArrayDeque<State>(); //bee states
    ArrayDeque<State> mq = new ArrayDeque<State>(); //mecho states

    for(int a = 0; a < n; a++){
      String row = br.readLine(); 
      for(int b = 0; b < n; b++){
        char cur = row.charAt(b);
        grid[a][b] = cur; 

        if(cur == 'M'){
          mq.add(new State(a,b,0));
          mechox = a; 
          mechoy = b; 
          mecho[a][b] = 0; 
        }
        else if(cur == 'H'){
          bq.add(new State(a,b,0));
          bees[a][b] = 0; 
        }
        else if(cur == 'D'){
          denx = a; 
          deny = b; 
        }
      }
    }

    while(!bq.isEmpty()){
      State cur = bq.poll();         
      for(int a = 0; a < 4; a++){
        int xcoor = xc[a] + cur.x; 
        int ycoor = yc[a] + cur.y; 
        if(xcoor < 0 || ycoor < 0 || xcoor >= n || ycoor >= n || grid[xcoor][ycoor] == 'T' || grid[xcoor][ycoor] == 'D' || bees[xcoor][ycoor] != max) continue;
        bees[xcoor][ycoor] = cur.cost + 1; 
        bq.add(new State(xcoor, ycoor, cur.cost + 1));
      }
    }
    while(!mq.isEmpty()){
      State cur = mq.poll(); 
      for(int a = 0; a < 4; a++){
        int xcoor = xc[a] + cur.x; 
        int ycoor = yc[a] + cur.y; 
        if(xcoor < 0 || ycoor < 0 || xcoor >= n || ycoor >= n || grid[xcoor][ycoor] == 'T' || grid[xcoor][ycoor] == 'H' || mecho[xcoor][ycoor] != max) continue; 
        mecho[xcoor][ycoor] = (cur.cost + 1 + s-1)/s; 
        mq.add(new State(xcoor, ycoor, cur.cost + 1));
      }
    }

    //for(long[] row : mecho) System.out.println(Arrays.toString(row));
    //System.out.println("mecho ^ bees v");
    //for(long[] row : bees) System.out.println(Arrays.toString(row));

    long min = 0; 
    long max = n*n; //best case it takes the bees n*m time to reach Mecho/Mecho is able to evade the bees for n*m time
    while(min < max){
      long mid = (min + max + 1)/2; 
      //System.out.println(min + " " + mid + " " + max);
      if(valid(mid)) min = mid; 
      else max = mid - 1; //want to maximize answer
    }      
    if(min > 0 || valid(min)) System.out.println(min);
    else System.out.println(-1);
    br.close();
  }
  public static boolean valid(long x){
    long[][] distance = new long[n][n]; 
    for(long[] row : distance) Arrays.fill(row, max);
    distance[mechox][mechoy] = 0; 
    ArrayDeque<Point> ad = new ArrayDeque<Point>(); 
    ad.add(new Point(mechox, mechoy));
    while(!ad.isEmpty()){
      Point cur = ad.poll(); 
      for(int a = 0; a < 4; a++){
        int xcoor = xc[a] + cur.x; 
        int ycoor = yc[a] + cur.y; 
        if(xcoor < 0 || ycoor < 0 || xcoor >= n || ycoor >= n || distance[xcoor][ycoor] != max || mecho[xcoor][ycoor] == max || mecho[xcoor][ycoor] + x > bees[xcoor][ycoor]) continue; 
        if(mecho[xcoor][ycoor] + x < bees[xcoor][ycoor]){
          ad.add(new Point(xcoor, ycoor));
          distance[xcoor][ycoor] = distance[cur.x][cur.y] + 1;
        }
        else if(mecho[xcoor][ycoor] + x == bees[xcoor][ycoor] && (distance[cur.x][cur.y] + 1) % s != 0){
          ad.add(new Point(xcoor, ycoor));
          distance[xcoor][ycoor] = distance[cur.x][cur.y] + 1;
        }
      }
    }
    return distance[denx][deny] != max;
  }
}

class Point{
  int x; 
  int y; 
  public Point(int xc, int yc){
    x = xc; 
    y = yc; 
  }
  public String toString(){
    return x + " " + y; 
  }
}

class State{
  int x; 
  int y; 
  long cost; 
  public State(int xc, int yc, long c){
    x = xc;
    y = yc; 
    cost = c; 
  }
  public String toString(){
    return x + " " + y + " " + cost; 
  }
}

Compilation message

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