답안 #587492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587492	2022-07-02T01:43:28 Z	PikaChu999	Mecho (IOI09_mecho)	Java 11	64 / 100	1000 ms	38304 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 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;
					if (xc == denx && yc == deny) {
						return true;
					}
          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 false;
  }
  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

64.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	64 ms	8224 KB	Output is correct
2	Correct	66 ms	8380 KB	Output is correct
3	Correct	58 ms	8264 KB	Output is correct
4	Correct	57 ms	8384 KB	Output is correct
5	Correct	56 ms	8344 KB	Output is correct
6	Correct	61 ms	8404 KB	Output is correct
7	Execution timed out	1068 ms	32960 KB	Time limit exceeded
8	Correct	61 ms	8348 KB	Output is correct
9	Correct	62 ms	8408 KB	Output is correct
10	Correct	105 ms	14204 KB	Output is correct
11	Correct	110 ms	13872 KB	Output is correct
12	Correct	164 ms	15524 KB	Output is correct
13	Correct	328 ms	18308 KB	Output is correct
14	Correct	67 ms	8576 KB	Output is correct
15	Correct	111 ms	14612 KB	Output is correct
16	Correct	112 ms	14432 KB	Output is correct
17	Correct	122 ms	14440 KB	Output is correct
18	Correct	114 ms	14436 KB	Output is correct
19	Correct	116 ms	14600 KB	Output is correct
20	Correct	111 ms	14016 KB	Output is correct
21	Correct	119 ms	14124 KB	Output is correct
22	Correct	211 ms	15300 KB	Output is correct
23	Correct	224 ms	15708 KB	Output is correct
24	Correct	249 ms	16032 KB	Output is correct
25	Correct	250 ms	16552 KB	Output is correct
26	Correct	270 ms	16192 KB	Output is correct
27	Correct	236 ms	16592 KB	Output is correct
28	Correct	303 ms	16556 KB	Output is correct
29	Correct	262 ms	16880 KB	Output is correct
30	Correct	330 ms	17100 KB	Output is correct
31	Correct	299 ms	17220 KB	Output is correct
32	Correct	332 ms	17920 KB	Output is correct
33	Correct	369 ms	22668 KB	Output is correct
34	Correct	422 ms	23060 KB	Output is correct
35	Correct	501 ms	23128 KB	Output is correct
36	Correct	422 ms	23556 KB	Output is correct
37	Correct	456 ms	23488 KB	Output is correct
38	Correct	541 ms	24080 KB	Output is correct
39	Correct	457 ms	23728 KB	Output is correct
40	Correct	464 ms	24012 KB	Output is correct
41	Correct	610 ms	23088 KB	Output is correct
42	Correct	489 ms	23592 KB	Output is correct
43	Correct	474 ms	24024 KB	Output is correct
44	Correct	653 ms	24136 KB	Output is correct
45	Correct	519 ms	25340 KB	Output is correct
46	Correct	493 ms	25188 KB	Output is correct
47	Correct	804 ms	25840 KB	Output is correct
48	Correct	521 ms	27144 KB	Output is correct
49	Correct	550 ms	27084 KB	Output is correct
50	Correct	810 ms	27700 KB	Output is correct
51	Correct	620 ms	29360 KB	Output is correct
52	Correct	613 ms	29236 KB	Output is correct
53	Correct	899 ms	29768 KB	Output is correct
54	Correct	610 ms	28924 KB	Output is correct
55	Correct	639 ms	29480 KB	Output is correct
56	Correct	964 ms	28452 KB	Output is correct
57	Correct	749 ms	30356 KB	Output is correct
58	Correct	790 ms	31396 KB	Output is correct
59	Execution timed out	1065 ms	30980 KB	Time limit exceeded
60	Correct	883 ms	36532 KB	Output is correct
61	Correct	944 ms	35660 KB	Output is correct
62	Execution timed out	1049 ms	32140 KB	Time limit exceeded
63	Execution timed out	1059 ms	34280 KB	Time limit exceeded
64	Execution timed out	1043 ms	34992 KB	Time limit exceeded
65	Execution timed out	1062 ms	35088 KB	Time limit exceeded
66	Execution timed out	1022 ms	33224 KB	Time limit exceeded
67	Correct	385 ms	24780 KB	Output is correct
68	Execution timed out	1056 ms	32520 KB	Time limit exceeded
69	Execution timed out	1018 ms	36140 KB	Time limit exceeded
70	Execution timed out	1037 ms	35824 KB	Time limit exceeded
71	Execution timed out	1053 ms	34492 KB	Time limit exceeded
72	Execution timed out	1062 ms	31836 KB	Time limit exceeded
73	Execution timed out	1080 ms	35044 KB	Time limit exceeded
74	Execution timed out	1068 ms	35964 KB	Time limit exceeded
75	Execution timed out	1082 ms	37884 KB	Time limit exceeded
76	Execution timed out	1068 ms	34944 KB	Time limit exceeded
77	Execution timed out	1089 ms	35008 KB	Time limit exceeded
78	Correct	330 ms	26568 KB	Output is correct
79	Execution timed out	1070 ms	37632 KB	Time limit exceeded
80	Execution timed out	1057 ms	37528 KB	Time limit exceeded
81	Execution timed out	1053 ms	38304 KB	Time limit exceeded
82	Execution timed out	1068 ms	37868 KB	Time limit exceeded
83	Execution timed out	1074 ms	37624 KB	Time limit exceeded
84	Execution timed out	1056 ms	34112 KB	Time limit exceeded
85	Execution timed out	1071 ms	37680 KB	Time limit exceeded
86	Execution timed out	1076 ms	37636 KB	Time limit exceeded
87	Execution timed out	1074 ms	34620 KB	Time limit exceeded
88	Execution timed out	1029 ms	37568 KB	Time limit exceeded
89	Execution timed out	1086 ms	37520 KB	Time limit exceeded
90	Execution timed out	1067 ms	33580 KB	Time limit exceeded
91	Execution timed out	1084 ms	33536 KB	Time limit exceeded
92	Execution timed out	1065 ms	37624 KB	Time limit exceeded