import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.StringTokenizer; public class Main{ static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; static char[][] map; static boolean[][] visited; static boolean[][] visitedLoc; static List loc; static List fire; static int h, w, startX, startY, fireX, fireY, rst; static BufferedWriter bw; static void fireBFS(int fireX, int fireY) throws IOException { Queue queue = new LinkedList<>(); for(int[] k : fire) { visited[k[0]][k[1]] = true; queue.add(new int[] {k[0], k[1]}); } int time = 0; boolean isPossible = false; while(!queue.isEmpty()) { int size = queue.size(); for(int i = 0; i < size; i++) { int[] curr = queue.poll(); int x = curr[0]; int y = curr[1]; for(int d = 0; d < 4; d++) { int nx = x + dx[d]; int ny = y + dy[d]; if(nx >= 0 && ny >= 0 && nx < h && ny < w) { if(!visited[nx][ny] && map[nx][ny] != '#') { visited[nx][ny] = true; map[nx][ny] = '*'; queue.add(new int[] {nx, ny}); } } } } time++; if(move(map, loc, time)) { isPossible = true; break; } } if(isPossible) { bw.write(rst + "\n"); } else { bw.write("IMPOSSIBLE\n"); } } static boolean move(char[][] map, List loc, int time) { Queue queue = new LinkedList<>(); for(int[] k : loc) { visitedLoc[k[0]][k[1]] = true; queue.add(k); } loc.clear(); while(!queue.isEmpty()) { int[] curr = queue.poll(); int x = curr[0]; int y = curr[1]; if(x == h-1 || y == w-1 || x == 0 || y == 0) { rst = time; return true; } for(int i = 0; i < 4; i ++) { int nx = x + dx[i]; int ny = y + dy[i]; if(nx >= 0 && ny >= 0 && nx < h && ny < w) { if(!visitedLoc[nx][ny] && map[nx][ny] == '.') { visitedLoc[nx][ny] = true; loc.add(new int[] {nx, ny}); } } } // for(int i = 0; i < h; i++) { // for(int j = 0; j < w; j++) { // System.out.print(map[i][j]); // } // System.out.println(); // } // for(int[] check : loc) { // System.out.println(Arrays.toString(check)); // } // System.out.println("---------------"); } return false; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); bw = new BufferedWriter(new OutputStreamWriter(System.out)); int T = Integer.parseInt(br.readLine()); for(int tc = 1; tc <= T; tc++) { StringTokenizer st = new StringTokenizer(br.readLine()); w = Integer.parseInt(st.nextToken());//너비 h = Integer.parseInt(st.nextToken()); //높이 map = new char[h][w]; fire = new LinkedList<>(); for(int i = 0; i < h; i++) { String input = br.readLine(); for(int j = 0; j < w; j++) { map[i][j] = input.charAt(j); if(map[i][j] == '@') { startX = i; startY = j; } else if(map[i][j] == '*') { fire.add(new int[] {i, j}); } } } visited = new boolean[h][w]; visitedLoc = new boolean[h][w]; loc = new LinkedList<>(); loc.add(new int[] {startX, startY}); fireBFS(fireX, fireY); } bw.flush(); } }

제출 #56060

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: