Submission #847668

#	Time	Username	Problem	Language	Result	Execution time	Memory
847668		Oz121	Mecho (IOI09_mecho)	Java	84 / 100	1068 ms	43420 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 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();
        //printMat(dis);
        //System.out.println();
        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]-1;

        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]-(time+1)/s);

                if (disB[nx][ny]<val) {
                    disB[nx][ny] = val;

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

        //int ans = -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;
        }
    }
}

• Subtask 1: 84 / 100