#include #include #include #include #include using namespace std; struct Node { int row; int col; }; int row, col; Node jihoon; vector fire; int dy[] = { -1, 1, 0, 0 }; int dx[] = { 0, 0, -1, 1 }; vector> map; // 입력 받은 맵 정보 vector> jiTime; // 지훈이 이동 시간 vector> fireTime; // 불 번지는 시간 // Flood Fill 수행 void fire_bfs() { queue que; for (int i = 0; i < fire.size(); i++) { Node temp = fire[i]; que.push(temp); fireTime[temp.row][temp.col] = 1; } while (!que.empty()) { Node now = que.front(); que.pop(); for (int i = 0; i < 4; i++) { int ny = now.row + dy[i]; int nx = now.col + dx[i]; if (ny < 0 || ny >= row || nx < 0 || nx >= col) continue; if (map[ny][nx] != 0) continue; if (fireTime[ny][nx] != 0 && fireTime[ny][nx] < fireTime[now.row][now.col] + 1) { continue; } fireTime[ny][nx] = fireTime[now.row][now.col] + 1; que.push({ ny, nx }); } } } void jihoon_bfs(Node start) { queue que; que.push(start); jiTime[start.row][start.col] = 1; while (!que.empty()) { Node now = que.front(); que.pop(); for (int i = 0; i < 4; i++) { int ny = now.row + dy[i]; int nx = now.col + dx[i]; if (ny < 0 || ny >= row || nx < 0 || nx >= col) continue; if (map[ny][nx] != 0) continue; if (jiTime[ny][nx] != 0 && jiTime[ny][nx] < jiTime[now.row][now.col] + 1) { continue; } jiTime[ny][nx] = jiTime[now.row][now.col] + 1; que.push({ ny, nx }); } } } // main 함수 시작 int main() { cin >> row >> col; map.resize(row, vector(col, 0)); jiTime.resize(row, vector(col, 0)); fireTime.resize(row, vector(col, 0)); for (int i = 0; i < row; i++) { string temp; cin >> temp; for (int j = 0; j < col; j++) { if (temp[j] == '#') { map[i][j] = 1; // 벽 } else { map[i][j] = 0; // 길 (갈 수 있는 곳) if (temp[j] == 'J') { jihoon = { i, j }; // 지훈이 시작 위치 } if (temp[j] == 'F') { fire.push_back({ i, j }); // 불 위치 } } } } // 지훈이 시간 탐색 jihoon_bfs(jihoon); // 불 번지는 시간 탐색 fire_bfs(); bool isPossible = false; int resTime = INT_MAX; // 불 번지는 시간과 지훈이 이동 시간 비교 for (int i = 0; i < row; i++) { if (i == 0 || i == row - 1) { for (int j = 0; j < col; j++) { if (jiTime[i][j] == 0) continue; if (jiTime[i][j] < fireTime[i][j] || (jiTime[i][j] > 0 && fireTime[i][j] == 0)) { if (resTime > jiTime[i][j]) { resTime = jiTime[i][j]; isPossible = true; } } } } else { if (jiTime[i][0] == 0 || jiTime[i][0] >= fireTime[i][0]) continue; if (jiTime[i][col - 1] == 0 || jiTime[i][col - 1] >= fireTime[i][col - 1]) continue; if (resTime > jiTime[i][0] || (jiTime[i][0] > 0 && fireTime[i][0] == 0)) { resTime = jiTime[i][0]; isPossible = true; } if (resTime > jiTime[i][col - 1] || (jiTime[i][col - 1] > 0 && fireTime[i][col - 1] == 0)) { resTime = jiTime[i][col - 1]; isPossible = true; } } } //for (int i = 0; i < row; i++) { // for (int j = 0; j < col; j++) { // cout << jiTime[i][j] << " "; // } // cout << "\n"; //} //cout << "\n"; //for (int i = 0; i < row; i++) { // for (int j = 0; j < col; j++) { // cout << fireTime[i][j] << " "; // } // cout << "\n"; //} if (isPossible) { cout << resTime; } else { cout << "IMPOSSIBLE"; } return 0; }

제출 #24739

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: