import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; public class Main { static int w, h; static char[][] B; static int[] dx = { 1, -1, 0, 0 }; static int[] dy = { 0, 0, 1, -1 }; static boolean[][] visited; static Queue fireQ; static Queue sangQ; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); for (int tc = 1; tc <= T; tc++) { // 입력 String[] input = br.readLine().split(" "); w = Integer.parseInt(input[0]); h = Integer.parseInt(input[1]); B = new char[h][w]; visited = new boolean[h][w]; fireQ = new LinkedList<>(); sangQ = new LinkedList<>(); for (int i = 0; i < h; i++) { String row = br.readLine(); for (int j = 0; j < w; j++) { B[i][j] = row.charAt(j); if (B[i][j] == '*') // 불 위치 저장 fireQ.add(new int[] { i, j }); if (B[i][j] == '@') { // 상근 위치 저장 sangQ.add(new int[] { i, j }); visited[i][j] = true; // 방문 } } } // 로직 int result = bfs(); // 이동 if (result == -1) System.out.println("IMPOSSIBLE"); else System.out.println(result); } } public static int bfs() { // 시간 int time = 0; while (!sangQ.isEmpty()) { time++; // 1. 불 먼저 확산 for (int i = 0; i < fireQ.size(); i++) { int[] f = fireQ.poll(); for (int d = 0; d < 4; d++) { int nx = f[0] + dx[d]; int ny = f[1] + dy[d]; if (!inBounds(nx, ny) || B[nx][ny] == '#' || B[nx][ny] == '*') continue; B[nx][ny] = '*'; fireQ.add(new int[] { nx, ny }); } } // 2. 상근 한 칸 이동 for (int i = 0; i < sangQ.size(); i++) { int[] s = sangQ.poll(); for (int d = 0; d < 4; d++) { int nx = s[0] + dx[d]; int ny = s[1] + dy[d]; // 탈출 if (!inBounds(nx, ny)) return time; if (B[nx][ny] == '.' && !visited[nx][ny]) { visited[nx][ny] = true; sangQ.add(new int[] { nx, ny }); } } } } return -1; // 방문 불가 } public static boolean inBounds(int x, int y) { return x >= 0 && x < h && y >= 0 && y < w; } }

제출 #55369

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: