import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] dx = {0, 0, -1, 1}; int[] dy = {1, -1, 0, 0}; int T = Integer.parseInt(br.readLine()); // 테스트 개수 for (int i = 0; i < T; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); int w = Integer.parseInt(st.nextToken()); int h = Integer.parseInt(st.nextToken()); Queue q = new LinkedList<>(); Queue fq = new LinkedList<>(); int[][] board = new int[h][w]; int[][] fdp = new int[h][w]; int[][] sdp = new int[h][w]; boolean possible = false; for (int j = 0; j < h; j++) { String s = br.readLine(); for (int k = 0; k < s.length(); k++) { board[j][k] = s.charAt(k); if (board[j][k] == '*') { fq.add(new Pair(j, k)); } else if (board[j][k] == '@') { q.add(new Pair(j, k)); fdp[j][k] = -1; } else if (board[j][k] == '.') { fdp[j][k] = -1; sdp[j][k] = -1; } } } while (!fq.isEmpty()) { Pair cur = fq.poll(); for (int dir = 0; dir < 4; dir++) { int nx = cur.x + dx[dir]; int ny = cur.y + dy[dir]; if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue; if (fdp[nx][ny] >= 0 || board[nx][ny] == '#') continue; fq.add(new Pair(nx, ny)); fdp[nx][ny] = fdp[cur.x][cur.y] + 1; } } while (!q.isEmpty()) { Pair cur = q.poll(); for (int dir = 0; dir < 4; dir++) { int nx = cur.x + dx[dir]; int ny = cur.y + dy[dir]; if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue; if (nx == 0 || nx == h - 1 || ny == 0 || ny == w - 1) { System.out.println(sdp[cur.x][cur.y] + 1); possible = true; q.clear(); break; } if (sdp[nx][ny] >= 0 || board[nx][ny] == '#') continue; if (fdp[nx][ny] != -1 && fdp[nx][ny] <= sdp[cur.x][cur.y] + 1) continue; q.add(new Pair(nx, ny)); sdp[nx][ny] = sdp[cur.x][cur.y] + 1; } } if (!possible) System.out.println("IMPOSSIBLE"); } } private static class Pair { int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } } }

제출 #31218

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: