#include #include #include using namespace std; int P, R, C; vector>map; queue> fire; pair pos; int dy[4] = { -1,1,0,0 }; int dx[4] = { 0,0,-1,1 }; void draw_map(int R, int C) { for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { char c; cin >> c; map[i][j] = c; if (c == '*') { fire.push({ i,j }); } else if (c == '@') { pos = { i,j }; } } } } void debug(vector> vis1, vector>vis2) { cout << ".......................\n"; cout << "Test1\n"; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { cout << vis1[i][j]; } cout << "\n"; } cout << "Test2\n"; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { cout << vis2[i][j]; } cout << "\n"; } cout << ".......................\n"; } void sol_bfs() { queue, int>> q_arr; queue, int>> q_arr2; vector> visited(R, vector(C, 0)); vector> visited2(R, vector(C, 0)); //stack fire positions; while (!fire.empty()) { pair fpos = fire.front(); q_arr.push({ {fpos.first, fpos.second},0 }); visited[fpos.first][fpos.second] = 1; fire.pop(); } int tmp = 1e9; while (!q_arr.empty()) { pair, int> qpos = q_arr.front(); q_arr.pop(); for (int i = 0; i < 4; i++) { int ny = qpos.first.first + dy[i]; int nx = qpos.first.second + dx[i]; int day = qpos.second; if (ny >= 0 && ny < R && nx >= 0 && nx < C && map[ny][nx] != '#' && map[ny][nx] != '@' && !visited[ny][nx]) { visited[ny][nx] = ++day; q_arr.push({ {ny,nx},day }); } else if (ny < 0 || ny >= R || nx < 0 || nx >= C) { //if (tmp > day) tmp = day; tmp = day; } } } int tmp2 = 1e9; q_arr2.push({ {pos.first,pos.second},0 }); visited2[pos.first][pos.second] = 1; while (!q_arr2.empty()) { pair, int> qpos2 = q_arr2.front(); q_arr2.pop(); for (int i = 0; i < 4; i++) { int ny = qpos2.first.first + dy[i]; int nx = qpos2.first.second + dx[i]; int day = qpos2.second; if (ny >= 0 && ny < R && nx >= 0 && nx < C && map[ny][nx] != '#' && map[ny][nx] != '*' && !visited2[ny][nx]) { visited2[ny][nx] = ++day; q_arr2.push({ {ny,nx},day }); } else if (ny < 0 || ny >= R || nx < 0 || nx >= C) { if (tmp2 > day) tmp2 = day; } } } //debug(visited, visited2); // 탈줄 불가 if (tmp2 == 1e9) { cout << "IMPOSSIBLE\n"; } else if (tmp > tmp2) { //탈출 cout << tmp2 + 1 << "\n"; } else if (tmp <= tmp2) { cout << "IMPOSSIBLE\n"; } //cout << "TEST: " << tmp << ' ' << tmp2 << "\n"; } int main() { cin >> P; for (int p = 0; p < P; p++) { cin >> C >> R; map = vector>(R, vector(C, 0)); draw_map(R, C); sol_bfs(); } return 0; }

제출 #150995

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: