Submission #528628

# Submission time Handle Problem Language Result Execution time Memory
528628 2022-02-20T21:59:06 Z coderInTraining Mecho (IOI09_mecho) Java 11
0 / 100
160 ms 12372 KB
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;
        }
    }
}
# Verdict Execution time Memory Grader output
1 Runtime error 152 ms 12348 KB Execution failed because the return code was nonzero
2 Runtime error 151 ms 12052 KB Execution failed because the return code was nonzero
3 Runtime error 124 ms 12144 KB Execution failed because the return code was nonzero
4 Runtime error 130 ms 11988 KB Execution failed because the return code was nonzero
5 Runtime error 139 ms 12184 KB Execution failed because the return code was nonzero
6 Runtime error 138 ms 12304 KB Execution failed because the return code was nonzero
7 Runtime error 128 ms 12060 KB Execution failed because the return code was nonzero
8 Runtime error 131 ms 11940 KB Execution failed because the return code was nonzero
9 Runtime error 127 ms 11796 KB Execution failed because the return code was nonzero
10 Runtime error 136 ms 12048 KB Execution failed because the return code was nonzero
11 Runtime error 135 ms 12092 KB Execution failed because the return code was nonzero
12 Runtime error 137 ms 12256 KB Execution failed because the return code was nonzero
13 Runtime error 130 ms 12272 KB Execution failed because the return code was nonzero
14 Runtime error 127 ms 12012 KB Execution failed because the return code was nonzero
15 Runtime error 145 ms 11880 KB Execution failed because the return code was nonzero
16 Runtime error 132 ms 11948 KB Execution failed because the return code was nonzero
17 Runtime error 127 ms 12180 KB Execution failed because the return code was nonzero
18 Runtime error 130 ms 12064 KB Execution failed because the return code was nonzero
19 Runtime error 145 ms 11928 KB Execution failed because the return code was nonzero
20 Runtime error 148 ms 12116 KB Execution failed because the return code was nonzero
21 Runtime error 126 ms 12372 KB Execution failed because the return code was nonzero
22 Runtime error 130 ms 11980 KB Execution failed because the return code was nonzero
23 Runtime error 132 ms 11928 KB Execution failed because the return code was nonzero
24 Runtime error 138 ms 11848 KB Execution failed because the return code was nonzero
25 Runtime error 128 ms 11932 KB Execution failed because the return code was nonzero
26 Runtime error 139 ms 12052 KB Execution failed because the return code was nonzero
27 Runtime error 145 ms 12128 KB Execution failed because the return code was nonzero
28 Runtime error 127 ms 12012 KB Execution failed because the return code was nonzero
29 Runtime error 150 ms 11920 KB Execution failed because the return code was nonzero
30 Runtime error 132 ms 12220 KB Execution failed because the return code was nonzero
31 Runtime error 145 ms 12076 KB Execution failed because the return code was nonzero
32 Runtime error 126 ms 12020 KB Execution failed because the return code was nonzero
33 Runtime error 147 ms 12048 KB Execution failed because the return code was nonzero
34 Runtime error 134 ms 12132 KB Execution failed because the return code was nonzero
35 Runtime error 129 ms 12348 KB Execution failed because the return code was nonzero
36 Runtime error 125 ms 12196 KB Execution failed because the return code was nonzero
37 Runtime error 131 ms 11784 KB Execution failed because the return code was nonzero
38 Runtime error 135 ms 12032 KB Execution failed because the return code was nonzero
39 Runtime error 126 ms 12220 KB Execution failed because the return code was nonzero
40 Runtime error 130 ms 12084 KB Execution failed because the return code was nonzero
41 Runtime error 128 ms 11988 KB Execution failed because the return code was nonzero
42 Runtime error 141 ms 12116 KB Execution failed because the return code was nonzero
43 Runtime error 129 ms 12132 KB Execution failed because the return code was nonzero
44 Runtime error 132 ms 12184 KB Execution failed because the return code was nonzero
45 Runtime error 129 ms 12320 KB Execution failed because the return code was nonzero
46 Runtime error 127 ms 12040 KB Execution failed because the return code was nonzero
47 Runtime error 127 ms 12072 KB Execution failed because the return code was nonzero
48 Runtime error 137 ms 12240 KB Execution failed because the return code was nonzero
49 Runtime error 148 ms 12280 KB Execution failed because the return code was nonzero
50 Runtime error 128 ms 12268 KB Execution failed because the return code was nonzero
51 Runtime error 139 ms 12252 KB Execution failed because the return code was nonzero
52 Runtime error 128 ms 12236 KB Execution failed because the return code was nonzero
53 Runtime error 130 ms 12040 KB Execution failed because the return code was nonzero
54 Runtime error 133 ms 12048 KB Execution failed because the return code was nonzero
55 Runtime error 129 ms 12020 KB Execution failed because the return code was nonzero
56 Runtime error 133 ms 12164 KB Execution failed because the return code was nonzero
57 Runtime error 126 ms 12292 KB Execution failed because the return code was nonzero
58 Runtime error 126 ms 11928 KB Execution failed because the return code was nonzero
59 Runtime error 127 ms 12172 KB Execution failed because the return code was nonzero
60 Runtime error 152 ms 12128 KB Execution failed because the return code was nonzero
61 Runtime error 131 ms 12296 KB Execution failed because the return code was nonzero
62 Runtime error 126 ms 12344 KB Execution failed because the return code was nonzero
63 Runtime error 126 ms 12144 KB Execution failed because the return code was nonzero
64 Runtime error 131 ms 12028 KB Execution failed because the return code was nonzero
65 Runtime error 153 ms 12104 KB Execution failed because the return code was nonzero
66 Runtime error 127 ms 11956 KB Execution failed because the return code was nonzero
67 Runtime error 127 ms 12232 KB Execution failed because the return code was nonzero
68 Runtime error 127 ms 12084 KB Execution failed because the return code was nonzero
69 Runtime error 146 ms 12032 KB Execution failed because the return code was nonzero
70 Runtime error 133 ms 11996 KB Execution failed because the return code was nonzero
71 Runtime error 127 ms 12092 KB Execution failed because the return code was nonzero
72 Runtime error 127 ms 12340 KB Execution failed because the return code was nonzero
73 Runtime error 129 ms 11940 KB Execution failed because the return code was nonzero
74 Runtime error 133 ms 12096 KB Execution failed because the return code was nonzero
75 Runtime error 129 ms 12052 KB Execution failed because the return code was nonzero
76 Runtime error 124 ms 12056 KB Execution failed because the return code was nonzero
77 Runtime error 126 ms 12024 KB Execution failed because the return code was nonzero
78 Runtime error 145 ms 11976 KB Execution failed because the return code was nonzero
79 Runtime error 128 ms 12104 KB Execution failed because the return code was nonzero
80 Runtime error 127 ms 12112 KB Execution failed because the return code was nonzero
81 Runtime error 127 ms 12164 KB Execution failed because the return code was nonzero
82 Runtime error 125 ms 12028 KB Execution failed because the return code was nonzero
83 Runtime error 160 ms 11820 KB Execution failed because the return code was nonzero
84 Runtime error 126 ms 12212 KB Execution failed because the return code was nonzero
85 Runtime error 129 ms 12196 KB Execution failed because the return code was nonzero
86 Runtime error 133 ms 12092 KB Execution failed because the return code was nonzero
87 Runtime error 153 ms 12052 KB Execution failed because the return code was nonzero
88 Runtime error 142 ms 11984 KB Execution failed because the return code was nonzero
89 Runtime error 129 ms 12240 KB Execution failed because the return code was nonzero
90 Runtime error 126 ms 12248 KB Execution failed because the return code was nonzero
91 Runtime error 131 ms 12144 KB Execution failed because the return code was nonzero
92 Runtime error 153 ms 12104 KB Execution failed because the return code was nonzero