#include #include #include #include #include using namespace std; vector> MoveTo = { {0,1}, {0, -1}, {1,0}, {-1,0} }; void BFS(const pair Start, vector> &Ground, vector> &FireBox) { vector> hvis(Ground.size(), vector(Ground[0].size())); vector> fvis(Ground.size(), vector(Ground[0].size())); queue> hBox; queue> fBox; hBox.push(Start); bool isExit = false; hvis[Start.first][Start.second] = true; for (int i = 0; i < FireBox.size(); i++) { fBox.push(FireBox[i]); fvis[FireBox[i].first][FireBox[i].second] = true; } while (true) { if (hBox.empty() && fBox.empty()) { break; } if (!hBox.empty()) { pair x = hBox.front(); hBox.pop(); for (int i = 0; i < 4; i++) { try { pair NewPos(MoveTo[i].first + x.first, MoveTo[i].second + x.second); char Val = Ground.at(NewPos.first).at(NewPos.second); //벽 이거나 불이 번진 자리거나 이미 지나간 자리면 if (Val == '#' || fvis[NewPos.first][NewPos.second] || hvis[NewPos.first][NewPos.second]) { continue; } hvis[NewPos.first][NewPos.second] = true; hBox.push(NewPos); } catch (const out_of_range&) { isExit = true; break; // break면 탈출구를 찾음 } } } if (!fBox.empty()) { for (int j = 0; j < fBox.size(); j++) // 동시에 불이 퍼짐을 구현 { pair x = fBox.front(); fBox.pop(); for (int i = 0; i < 4; i++) { try { pair NewPos(MoveTo[i].first + x.first, MoveTo[i].second + x.second); char Val = Ground.at(NewPos.first).at(NewPos.second); if (Val == '#' || fvis[NewPos.first][NewPos.second]) { continue; } fvis[NewPos.first][NewPos.second] = true; fBox.push(NewPos); } catch (const out_of_range&) { continue; } } } } } if (isExit) { } else { cout << "IMPOSSIBLE"; } } int main() { int A, B; cin >> A >> B; vector> Ground(A, vector(B)); pair EntryPoint; vector> FireBox; for (int i = 0; i < A; i++) { for (int j = 0; j < B; j++) { char input; cin >> input; Ground[i][j] = input; if (input == 'J') { EntryPoint = make_pair(i, j); } else if (input == 'F') { FireBox.push_back(make_pair(i, j)); } } } BFS(EntryPoint, Ground, FireBox); return 0; }

제출 #27497

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: