제출 #847061

#제출 시각아이디문제언어결과실행 시간메모리
847061Oz121Mecho (IOI09_mecho)Java
38 / 100
1052 ms43796 KiB
import java.io.*; import java.util.*; public class mecho { public static char[][] arr; public static int[][] dis; public static int num; public static int s; public static int sx; public static int sy; public static ArrayDeque<Integer> Hqueue; public static int[] dx = {0,0,-1,1}; public static int[] dy = {-1,1,0,0}; public static void main(String[] args) throws IOException { BufferedReader scan = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer l1 = new StringTokenizer(scan.readLine()); num = Integer.parseInt(l1.nextToken()); s = Integer.parseInt(l1.nextToken()); arr = new char[num][num]; dis = new int[num][num]; Hqueue = new ArrayDeque<>(); for (int i = 0;i<num;i++) Arrays.fill(dis[i],Integer.MAX_VALUE); sx = -1; sy = -1; int ex = -1; int ey = -1; for (int i = 0;i<num;i++) { StringTokenizer st = new StringTokenizer(scan.readLine()); String s = st.nextToken(); for (int j = 0;j<num;j++) { arr[i][j] = s.charAt(j); if (arr[i][j]=='M') { sx = i; sy = j; } else if (arr[i][j]=='D') { ex = i; ey = j; } else if (arr[i][j]=='H') { Hqueue.add(i*num+j); dis[i][j] = 0; } } } bfsH(); int[][] ans = bfsB(); //printMat(ans); System.out.println(ans[ex][ey]); } public static int[][] bfsB () { //bfs for the bears ArrayDeque<Pair> bear = new ArrayDeque<>(); bear.add(new Pair(sx*num+sy,s)); int[][] disB = new int[num][num]; for (int i = 0;i<num;i++) Arrays.fill(disB[i], -1); disB[sx][sy] = dis[sx][sy]; while (!bear.isEmpty()) { Pair curr = bear.poll(); int node = curr.node; int time = curr.time; int x = node/num; int y = node%num; int minute = time/s; int sec = time%s; for (int i = 0;i<4;i++) { int nx = x+dx[i]; int ny = y+dy[i]; if (nx<0||ny<0||nx>=num||ny>=num) continue; //||dis[nx][ny]!=Integer.MAX_VALUE if (arr[nx][ny]=='T'||arr[nx][ny]=='H') continue; int val = Math.min(disB[x][y], dis[nx][ny]-minute); if (disB[nx][ny]<val) { disB[nx][ny] = val; bear.add(new Pair(nx*num+ny, minute*s+sec+1)); } } } return disB; } public static void bfsH () { //bfs for the bees while (!Hqueue.isEmpty()) { int curr = Hqueue.poll(); int x = curr/num; int y = curr%num; for (int i = 0;i<4;i++) { int nx = x+dx[i]; int ny = y+dy[i]; if (nx<0||ny<0||nx>=num||ny>=num||dis[nx][ny]!=Integer.MAX_VALUE) continue; if (arr[nx][ny]=='T'||arr[nx][ny]=='D') continue; dis[nx][ny] = dis[x][y]+1; Hqueue.add(nx*num+ny); } } } public static void printMat (int[][] arr) { for (int i = 0;i<arr.length;i++) { for (int j = 0;j<arr[0].length;j++) { System.out.print(arr[i][j]+" "); } System.out.println(); } } public static class Pair { int node; int time; Pair (int node, int time) { this.node = node; this.time = time; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...