#include #include #include #include using namespace std; const char WALL = '#'; const char JIHOON = 'J'; const char FIRE = 'F'; pair dirs[4] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; bool is_in_boundary(pair& pos, short r, short c) { if (pos.first < 0 || pos.first >= r || pos.second < 0 || pos.second >= c) { return false; } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); queue, int>> qu; queue> fire_qu; short r, c; cin >> r >> c; vector> maze(r, vector(c)); vector> fires(r, vector(c, -1)); for (short i = 0; i < r; i++) { string input; cin >> input; for (short j = 0; j < c; j++) { maze[i][j] = input[j]; if (maze[i][j] == FIRE) { fires[i][j] = 0; fire_qu.push({i, j}); } else if (maze[i][j] == JIHOON) { qu.push({{i, j}, 0}); } } } while (!fire_qu.empty()) { pair& f = fire_qu.front(); fire_qu.pop(); int next_t = fires[f.first][f.second] + 1; for (int i = 0; i < 4; i++) { pair next_pos = {f.first + dirs[i].first, f.second + dirs[i].second}; if (!is_in_boundary(next_pos, r, c) || maze[next_pos.first][next_pos.second] == WALL) { continue; } if (fires[next_pos.first][next_pos.second] == -1 || fires[next_pos.first][next_pos.second] > next_t) { fires[next_pos.first][next_pos.second] = next_t; fire_qu.push(next_pos); } } } while (!qu.empty()) { pair, int>& f = qu.front(); qu.pop(); pair& pos = f.first; int next_t = f.second + 1; for (int i = 0; i < 4; i++) { pair next_pos = {pos.first + dirs[i].first, pos.second + dirs[i].second}; if (!is_in_boundary(next_pos, r, c)) { cout << next_t << '\n'; return 0; } if (maze[next_pos.first][next_pos.second] == WALL || maze[next_pos.first][next_pos.second] == JIHOON) continue; if (fires[next_pos.first][next_pos.second] >= 0 && fires[next_pos.first][next_pos.second] <= next_t) continue; maze[next_pos.first][next_pos.second] = JIHOON; qu.push({next_pos, next_t}); } } cout << "IMPOSSIBLE" << '\n'; return 0; }

제출 #39821

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: