#include #include #include using namespace std; /** * 미로 탈출 * * BFS * 1. 불의 이동위치를 구한다 * - 불은 벽통과x, 범위넘기x * 2. 지훈이 이동위치를 구한다 * - 이동 못하는 경우 IMPOSSIBLE * - 벽통과x * - 가장자리일경우,탈출 성공 * * */ int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int main() { int N, M; cin >> N >> M; vector area(N, ""); vector> visited(N, vector(M, false)); queue, int>> person; queue> fire; int answer = 99999; // ✅ 입력 방식 수정: 한 줄씩 입력 for (int i = 0; i < N; i++) { cin >> area[i]; for (int j = 0; j < M; j++) { if (area[i][j] == 'J') { person.push({{i, j}, 0}); visited[i][j] = true; } else if (area[i][j] == 'F') { fire.push({i, j}); } } } while(!person.empty()) { queue> temp = fire; while(!temp.empty()) { int fx = temp.front().first; int fy = temp.front().second; temp.pop(); fire.pop(); for(int i=0; i<4; i++) { int xx = fx + dx[i]; int yy = fy + dy[i]; if(xx<0 || yy<0 || xx>=N || yy >=M) continue; if(area[xx][yy]=='#' || area[xx][yy]=='F') continue; area[xx][yy] = 'F'; fire.push({xx, yy}); } } int px = person.front().first.first; int py = person.front().first.second; int pcnt = person.front().second; person.pop(); bool flag = false; if(px==0 || py==0 || px==N-1 || py==M-1) { answer = min(answer, pcnt+1); continue; } for(int i=0; i<4; i++) { int xx = px + dx[i]; int yy = py + dy[i]; if(xx<0 || yy<0 || xx>=N || yy>=M || visited[xx][yy]) continue; if(area[xx][yy]=='#' || area[xx][yy]=='F') continue; visited[xx][yy] = true; person.push({{xx, yy}, pcnt+1}); flag = true; } if(!flag) { // cout << px << ' ' << py << ' ' << pcnt << endl; cout << "IMPOSSIBLE"; exit(0); } } if(answer == 99999) { cout << "IMPOSSIBLE"; exit(0); } cout << answer; return 0; } // 3:22

제출 #39561

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: