제출 #528628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528628		coderInTraining	Mecho (IOI09_mecho)	Java	0 / 100	160 ms	12372 KiB

mecho

import java.util.*;

class Main {

    public static int mechoX;
    public static int mechoY;

    public static int denX;
    public static int denY;
    public static void main (String[]args) {
        Scanner scan = new Scanner (System.in);

        int sideLength = scan.nextInt();
        int maxSteps = scan.nextInt();

        char [][] grid = new char [sideLength][sideLength];

        Queue <Pair> queue = new LinkedList <Pair>();

        mechoX = 0;
        mechoY = 0;

        denX = 0;
        denY = 0;

        int [][] beeDistances = new int [sideLength][sideLength];

        for (int i = 0; i < sideLength; i++) {
            Arrays.fill(beeDistances[i], Integer.MAX_VALUE);
        }


        for (int i = 0; i < sideLength; i++) {
            String line = scan.next();

            for (int j = 0; j < sideLength; j++) {
                grid[i][j] = line.charAt(j);

                if (grid[i][j] == 'H') {
                    beeDistances[i][j] = 0;
                    Pair addingPair = new Pair (i, j);
                    queue.add(addingPair);
                }

                if (grid[i][j] == 'M') {
                    mechoX = i;
                    mechoY = j;
                }

                if (grid[i][j] == 'D') {
                    denX = i;
                    denY = j;
                }
            }
        }
        
        while (queue.isEmpty() == false) {
            Pair curPair = queue.poll();

            int curRow = curPair.row;
            int curCol = curPair.column;
            int cDist = beeDistances[curRow][curCol];

            if ((curRow - 1 >= 0) && ((grid[curRow - 1][curCol] == 'G') || (grid[curRow - 1][curCol] == 'M'))) {
                if (cDist + 1 < beeDistances[curRow - 1][curCol]) {
                    beeDistances[curRow - 1][curCol] = cDist + 1;
                    Pair addingPair = new Pair (curRow - 1, curCol);
                    queue.add(addingPair);
                }
            }

            if ((curCol + 1 < sideLength) && ((grid[curRow][curCol + 1] == 'G') || (grid[curRow][curCol + 1] == 'M'))) {
                if (cDist + 1 < beeDistances[curRow][curCol + 1]) {
                    beeDistances[curRow][curCol + 1] = cDist + 1;
                    Pair addingPair = new Pair (curRow, curCol + 1);
                    queue.add(addingPair);
                }
            }

            if ((curRow + 1 < sideLength) && ((grid[curRow + 1][curCol] == 'G') || (grid[curRow + 1][curCol] == 'M'))) {
                if (cDist + 1 < beeDistances[curRow + 1][curCol]) {
                    beeDistances[curRow + 1][curCol] = cDist + 1;
                    Pair addingPair = new Pair (curRow + 1, curCol);
                    queue.add(addingPair);
                }
            }

            if ((curCol - 1 >= 0) && ((grid[curRow][curCol - 1] == 'G') || (grid[curRow][curCol - 1] == 'M'))) {
                if (cDist + 1 < beeDistances[curRow][curCol - 1]) {
                    beeDistances[curRow][curCol - 1] = cDist + 1;
                    Pair addingPair = new Pair (curRow, curCol - 1);
                    queue.add(addingPair);
                }
            }
        }

        // Program works so far

        int lowerBound = 0;
        int upperBound = beeDistances[mechoX][mechoY];

        int lastWorkingMiddle = -1;
        int lastMiddle = -1;

        while (lowerBound <= upperBound) {
            int middle = (lowerBound + upperBound + 1) / 2;

            if (lastMiddle == middle) {
                break;
            }
            lastMiddle = middle;

            if (bfsSimulation(middle, maxSteps, grid, beeDistances)) {
                lowerBound = middle;
                lastWorkingMiddle = middle;
            }
            else {
                upperBound = middle;
            }
        }

        if (bfsSimulation(0, maxSteps, grid, beeDistances)) {
            lastWorkingMiddle = Math.max(lastWorkingMiddle, 0);
        }

        System.out.println(lastWorkingMiddle);
    }

    public static boolean bfsSimulation (int waitingTime, int maxSteps, char [][] grid, int [][] beeDistances) {
        int sideLength = grid.length;
        
        boolean [][] visited = new boolean [sideLength][sideLength];
        boolean [][] workingVisited = new boolean [sideLength][sideLength];

        Triplet startingPair = new Triplet (mechoX, mechoY, 0);
        Queue <Triplet> queue = new LinkedList <Triplet>();
        queue.add(startingPair);

        visited[mechoX][mechoY] = true;
        workingVisited[mechoX][mechoY] = true;

        while (queue.isEmpty() == false) {
            Triplet curTriplet = queue.poll();

            int curX = curTriplet.row;
            int curY = curTriplet.column;
            int cDist = curTriplet.distance;

            ArrayList<Pair> neighborsWithinOne = neighbors(curX, curY, maxSteps, grid);

            for (int i = 0; i < neighborsWithinOne.size(); i++) {
                Pair curPair = neighborsWithinOne.get(i);
                int nextR = curPair.row;
                int nextC = curPair.column;

                boolean hasNeighbor = false;
                if ((nextR - 1 >= 0) && (workingVisited[nextR - 1][nextC])) {
                    hasNeighbor = true;
                }

                if ((nextC + 1 < sideLength) && (workingVisited[nextR][nextC + 1])) {
                    hasNeighbor = true;
                }

                if ((nextR + 1 < sideLength) && (workingVisited[nextR + 1][nextC])) {
                    hasNeighbor = true;
                }

                if ((nextC - 1 >= 0) && (workingVisited[nextR][nextC - 1])) {
                    hasNeighbor = true;
                }

                if ((cDist + waitingTime < beeDistances[nextR][nextC]) && (visited[nextR][nextC] == false) && (hasNeighbor)) {
                    visited[nextR][nextC] = true;
                    Triplet addingTriplet = new Triplet (nextR, nextC, cDist + 1);
                    queue.add(addingTriplet);
                    workingVisited[nextR][nextC] = true;
                }
                else if (visited[nextR][nextC] == false) {
                    visited[nextR][nextC] = true;
                }
            }
        }

        return (workingVisited[denX][denY]);
    }

    public static ArrayList<Pair> neighbors (int startX, int startY, int maxSteps, char [][] grid) {
        ArrayList<Pair> answerList = new ArrayList<Pair>();

        Triplet startingPair = new Triplet (startX, startY, 0);
        Queue <Triplet> queue = new LinkedList <Triplet>();
        queue.add(startingPair);

        int sideLength = grid.length;

        boolean [][] visited = new boolean [sideLength][sideLength];
        visited[startX][startY] = true;

        while (queue.isEmpty() == false) {
            Triplet curPair = queue.poll();

            int curX = curPair.row;
            int curY = curPair.column;
            int cDist = curPair.distance;

            if (cDist <= maxSteps) {
                Pair addingPair = new Pair (curX, curY);
                answerList.add(addingPair);
            }

            if (cDist == maxSteps) {
                continue;
            }

            if ((curX - 1 >= 0) && (visited[curX - 1][curY] == false) && (((grid[curX - 1][curY] == 'G')) || (grid[curX - 1][curY] == 'D'))) {
                Triplet addingTriplet = new Triplet (curX - 1, curY, cDist + 1);
                queue.add(addingTriplet);
                visited[curX - 1][curY] = true;
            }

            if ((curY + 1 < sideLength) && (visited[curX][curY + 1] == false) && ((grid[curX][curY + 1] == 'G') || (grid[curX][curY + 1] == 'D'))) {
                Triplet addingTriplet = new Triplet (curX, curY + 1, cDist + 1);
                queue.add(addingTriplet);
                visited[curX][curY + 1] = true;
            }

            if ((curX + 1 < sideLength) && (visited[curX + 1][curY] == false) && ((grid[curX + 1][curY] == 'G') || (grid[curX + 1][curY] == 'D'))) {
                Triplet addingTriplet = new Triplet (curX + 1, curY, cDist + 1);
                queue.add(addingTriplet);
                visited[curX + 1][curY] = true;
            }

            if ((curY - 1 >= 0) && (visited[curX][curY - 1] == false) && ((grid[curX][curY - 1] == 'G') || (grid[curX][curY - 1] == 'D'))) {
                Triplet addingTriplet = new Triplet (curX, curY - 1, cDist + 1);
                queue.add(addingTriplet);
                visited[curX][curY - 1] = true;
            }
        }

        return (answerList);
    }

    private static class Triplet {
        int row;
        int column;
        int distance;

        public Triplet (int row, int column, int distance) {
            this.row = row;
            this.column = column;
            this.distance = distance;
        }
    }

    private static class Pair {
        int row;
        int column;

        public Pair (int row, int column) {
            this.row = row;
            this.column = column;
        }
    }
}

• Subtask 1: 0 / 100