| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 528628 | 2022-02-20T21:59:06 Z | coderInTraining | Mecho (IOI09_mecho) | Java 11 | 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 |