#include using namespace std; #define x second #define y first const int dx[4] = {0, 1, 0, -1}; const int dy[4] = {1, 0, -1, 0}; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); bool canEscape = false; int ret = 0; // I-1. R, C ( 1 <= R, C <= 1000 ) // R = 미로 행의 개수, C = 열의 개수 int r, c; cin >> r >> c; // I-2. R줄 동안 미로 행이 주어짐 // # - 벽 // . - 지나갈 수 있는 공간 // J - 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간) // F - 불이 난 공간 vector vs_map(r); vector> vvi_visited(r, vector(c, -1)); vector> vpii_fire; queue> qpii_bfs; for(int i = 0; i < r; ++i) { cin >> vs_map[i]; } // S-1. 초기 불의 위치와 지훈이의 위치 찾기, (지훈이 먼저) for(int i = 0; i < r; ++i) { for(int j = 0; j < c; ++j) { if(vs_map[i][j] == 'J') { qpii_bfs.push({i, j}); vvi_visited[i][j] = 1; } if(vs_map[i][j] == 'F') { vpii_fire.push_back({i, j}); } } } for(size_t i = 0; i < vpii_fire.size(); ++i) { qpii_bfs.push(vpii_fire[i]); } // S-2. BFS 돌리기 // Visited => 지훈: 1, 기본: -1 // 불은 맵에서 직접 바꿔줄 것 while(qpii_bfs.empty() == false) { pair node = qpii_bfs.front(); qpii_bfs.pop(); for(int dir = 0; dir < 4; ++dir) { int nx = node.x + dx[dir]; int ny = node.y + dy[dir]; if(nx < 0 || ny < 0 || ny >= r || nx >= c) { // 지훈이가 가장자리 도달 if(vvi_visited[node.y][node.x] > 0) { canEscape = true; ret = vvi_visited[node.y][node.x]; break; } // 불이 가장자리 도달 else { continue; } } if(vs_map[ny][nx] == 'F' || vvi_visited[ny][nx] != -1 || vs_map[ny][nx] == '#') { continue; } if(vs_map[ny][nx] != '.') { continue; } // 지훈이 if(vvi_visited[node.y][node.x] > 0) { vvi_visited[ny][nx] = vvi_visited[node.y][node.x] + 1; qpii_bfs.push({ny, nx}); } // 불 (-1) else { vs_map[ny][nx] = 'F'; qpii_bfs.push({ny, nx}); } } if(canEscape == true) { break; } } // O-1. 지훈이가 불에 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 출력 // 탈출할 수 있는 경우 가장 빠른 탈출시간 if(canEscape == true) { cout << ret; } else { cout << "IMPOSSIBLE"; } return 0; }

제출 #11817

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: