Submission #847649

#	Time	Username	Problem	Language	Result	Execution time	Memory
847649		Oz121	Mecho (IOI09_mecho)	Java	26 / 100	420 ms	39192 KiB

mecho

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 int ex; public static int ey;
    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; ex = -1; 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 low = 0; int high = num;
        while (low<high) {
            int mid = (low+high+1)/2;

            if (bfsB(mid)) {
                low = mid;
            } else {
                high = mid-1;
            }

        }

        System.out.println(low);
    }

    public static boolean bfsB (int eat) { //bfs for the bears
        ArrayDeque<Pair> bear = new ArrayDeque<>();
        bear.add(new Pair(sx*num+sy,eat*s));

        boolean[][] visited = new boolean[num][num];
        visited[sx][sy] = true;

        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||visited[nx][ny]) continue; //||dis[nx][ny]!=Integer.MAX_VALUE
                if (arr[nx][ny]=='T'||arr[nx][ny]=='H') continue;

                if ((time+1)/s<dis[nx][ny]) {
                    visited[nx][ny] = true;

                    bear.add(new Pair(nx*num+ny, time+1));
                }
            }
        }

        return visited[ex][ey];
    }

    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;
        }
    }
}

• Subtask 1: 26 / 100