import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Arrays; import java.util.Queue; import java.util.ArrayDeque; public class Main { private static int swanIndex = 0; private static final int WATER = 0; private static final int SWAN_1 = 1; private static final int SWAN_2 = 2; public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String[] sizeTokens = reader.readLine().split(" "); int height = Integer.parseInt(sizeTokens[0]); int width = Integer.parseInt(sizeTokens[1]); char[][] originalMap = new char[height][]; for (int y = 0; y < height; y++) { originalMap[y] = reader.readLine().toCharArray(); } LocInfo[][] infoMap = new LocInfo[height][width]; Queue boundaryQueue = new ArrayDeque<>(); for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { if (originalMap[y][x] == 'X') { continue; } if (infoMap[y][x] != null) { continue; } int tempSwanIndex = swanIndex; drawInfoMapAndFindBoundary(originalMap, infoMap, new Location(y, x), boundaryQueue); if (swanIndex - tempSwanIndex == 2) { System.out.println(0); return; } } } int time = calculateTime(infoMap, boundaryQueue); System.out.println(time); reader.close(); } private static int calculateTime(LocInfo[][] infoMap, Queue locQueue) { int height = infoMap.length; int width = infoMap[0].length; int[] dy = new int[] {-1, 0, 1, 0}; int[] dx = new int[] {0, -1, 0, 1}; int[][] meltingTime = new int[height][width]; int time = -1; while (!locQueue.isEmpty()) { time++; int queueSize = locQueue.size(); for (int locIndex = 0; locIndex < queueSize; locIndex++) { Location loc = locQueue.poll(); LocInfo info = infoMap[loc.y][loc.x]; for (int direction = 0; direction < dy.length; direction++) { int newY = loc.y + dy[direction]; int newX = loc.x + dx[direction]; if (newY < 0 || newY >= height || newX < 0 || newX >= width) { continue; } if (infoMap[newY][newX] != null) { continue; } infoMap[newY][newX] = info; locQueue.offer(new Location(newY, newX)); meltingTime[newY][newX] = time; } } queueSize = locQueue.size(); for (int locIndex = 0; locIndex < queueSize; locIndex++) { Location loc = locQueue.poll(); LocInfo info = infoMap[loc.y][loc.x]; for (int direction = 0; direction < dy.length; direction++) { int newY = loc.y + dy[direction]; int newX = loc.x + dx[direction]; if (newY < 0 || newY >= height || newX < 0 || newX >= width) { continue; } LocInfo another = infoMap[newY][newX]; if (another == null) { continue; } if (info.value == WATER && another.value != WATER) { info.value = another.value; } if (info.value != WATER && another.value == WATER) { another.value = info.value; } if (info.value + another.value == 3) { return time+1; } } locQueue.offer(loc); } } return -1; } private static void drawInfoMapAndFindBoundary(char[][] originalMap, LocInfo[][] map, Location start, Queue boundaryQueue) { LocInfo mark = new LocInfo(WATER); Queue locQueue = new ArrayDeque<>(); locQueue.offer(start); map[start.y][start.x] = mark; int height = map.length; int width = map[0].length; int[] dy = new int[] {-1, 0, 1, 0}; int[] dx = new int[] {0, -1, 0, 1}; while (!locQueue.isEmpty()) { Location loc = locQueue.poll(); if (originalMap[loc.y][loc.x] == 'L') { mark.value = ++swanIndex; } boolean isOffered = false; for (int direction = 0; direction < dy.length; direction++) { int newY = loc.y + dy[direction]; int newX = loc.x + dx[direction]; if (newY < 0 || newY >= height || newX < 0 || newX >= width) { continue; } if (originalMap[newY][newX] == 'X') { if (!isOffered) { isOffered = true; boundaryQueue.offer(loc); } continue; } if (map[newY][newX] != null) { continue; } map[newY][newX] = mark; locQueue.offer(new Location(newY, newX)); } } } private static class Location { int y, x; Location(int y, int x) { this.y = y; this.x = x; } } private static class LocInfo { int value; LocInfo(int value) { this.value = value; } @Override public String toString() { return value + ""; } } }

제출 #132807

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: