Submission #587489

#	Time	Username	Problem	Language	Result	Execution time	Memory
587489		PikaChu999	Mecho (IOI09_mecho)	Java	67 / 100	1098 ms	38004 KiB

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 mecho{
  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 int[] xcoors = {0,0,1,-1};
  public static int[] ycoors = {1,-1,0,0};
	public static int INF = 10000000;

  public static int denx; 
  public static int deny; //x y coordinates of mecho's house
  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]; 

    for(int a = 0; a < n; a++){
      String row = br.readLine(); 
      for(int b = 0; b < n; b++){
        grid[a][b] = row.charAt(b);
        if(grid[a][b] == 'D'){
          denx = a; 
          deny = b; 
        }
      }
    }
    
    int min = 0; 
    int 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

		if (!valid(0)) {
			System.out.println(-1);
		} else {
			while(min < max) {
        int mid = (min + max + 1)/2; 
        if(valid(mid)) min = mid; 
        else max = mid - 1; //want to maximize answer
      } 
      System.out.println(min);
		}

		//System.out.println(valid(3));
    br.close();
  }
  public static boolean valid(int headStart){ //how much head start the bees get
    ArrayDeque<Point> bees = new ArrayDeque<Point>(); 
    int[][] beeDist = new int[n][n]; 
    for(int[] row : beeDist) Arrays.fill(row, INF);
    ArrayDeque<Point> mecho = new ArrayDeque<Point>(); 
    int[][] mechoDist = new int[n][n]; 
    for(int[] row : mechoDist) Arrays.fill(row, INF);
    for(int a = 0; a < n; a++){
      for(int b = 0; b < n; b++){
        if(grid[a][b] == 'H'){
          bees.add(new Point(a,b));
          beeDist[a][b] = 0; 
        }
        else if(grid[a][b] == 'M'){
          mecho.add(new Point(a, b));
          mechoDist[a][b] = 0; 
        }
      }
    }

    //give bees headstart
    while(!bees.isEmpty()){
      Point cur = bees.peekFirst(); 
      if(beeDist[cur.x][cur.y] == headStart) break;
			bees.pollFirst();
			
      for(int a = 0; a < 4; a++){
        int xc = xcoors[a] + cur.x;
        int yc = ycoors[a] + cur.y; 
        if(outOfBounds(xc, yc) || beeDist[xc][yc] != INF || grid[xc][yc] == 'T' || grid[xc][yc] == 'D') continue;
        beeDist[xc][yc] = beeDist[cur.x][cur.y] + 1; 
        bees.add(new Point(xc, yc));
      }
    }

    //now do simultaneous mecho and bees bfs
    int round = 1; //mecho can be up to round * s steps away from starting point
    while(!mecho.isEmpty()){
      //mecho moves
      while(!mecho.isEmpty()){
        Point cur = mecho.peekFirst(); 
        if(mechoDist[cur.x][cur.y] >= round * s) break;
				mecho.pollFirst();
				if (beeDist[cur.x][cur.y] != INF) {
					//this cell has already been taken over by the bees, so Mecho cannot be here.
					continue;
				}
				
        for(int a = 0; a < 4; a++){
          int xc = xcoors[a] + cur.x;
          int yc = ycoors[a] + cur.y; 
          if(outOfBounds(xc, yc) || beeDist[xc][yc] != INF || mechoDist[xc][yc] != INF || grid[xc][yc] == 'T' || grid[xc][yc] == 'H') continue; 
          mechoDist[xc][yc] = mechoDist[cur.x][cur.y] + 1;
          mecho.add(new Point(xc, yc));
        }
      }
      //bees move
      while(!bees.isEmpty()){
        Point cur = bees.peekFirst(); 
        if(beeDist[cur.x][cur.y] >= headStart + round) break; 
        bees.pollFirst(); 
        for(int a = 0; a < 4; a++){
          int xc = xcoors[a] + cur.x; 
          int yc = ycoors[a] + cur.y; 
          if(outOfBounds(xc, yc) || beeDist[xc][yc] != INF || grid[xc][yc] == 'T' || grid[xc][yc] == 'D') continue; 
          beeDist[xc][yc] = beeDist[cur.x][cur.y] + 1; 
          bees.add(new Point(xc, yc));
        }
      }
			
      round++; 
    }
    return mechoDist[denx][deny] != INF; 
  }
  public static boolean outOfBounds(int x, int y){
    if(x < 0 || y < 0 || x >= n || y >= n) return true; 
    return false; 
  }


	public static void debug(int[][] dist) {
  	for (int i = 0; i < n; i++) {
  		for (int j = 0; j < n; j++) {
  			if (dist[i][j] == INF)
  				System.out.print("I");
  			else
  				System.out.print(dist[i][j]);
  		}
  		System.out.println();
  	}
  }
}

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

• Subtask 1: 67 / 100