#include #include #include #include #include using namespace std; struct Node { int y, x; }; int N, M; char board[1001][1001]; vectorfires; int yst, xst; int fire_time[1001][1001]; int sg_time[1001][1001]; int dr[] = { -1,1,0,0 }; int dc[] = { 0,0,-1,1 }; bool isValid(int y, int x) { return y >= 0 && x >= 0 && y < N && x < M; } int main() { int T; cin >> T; for (int tc = 1; tc < T + 1; tc++) { memset(fire_time, -1, sizeof(fire_time)); memset(sg_time, -1, sizeof(sg_time)); cin >> M >> N; for (int i = 0; i < N; i++) { string input; cin >> input; for (int j = 0; j < M; j++) { board[i][j] = input[j]; if (board[i][j] == '*') { fires.push_back({ i,j }); } if (board[i][j] == '@') { yst = i; xst = j; } } } queueq_fire; for (Node fire : fires) { fire_time[fire.y][fire.x] = 0; q_fire.push({ fire.y,fire.x }); } while (!q_fire.empty()) { Node now = q_fire.front(); q_fire.pop(); for (int i = 0; i < 4; i++) { int ny = now.y + dr[i]; int nx = now.x + dc[i]; if (board[ny][nx] == '#')continue; if (isValid(ny, nx) && fire_time[ny][nx] == -1) { fire_time[ny][nx] = fire_time[now.y][now.x] + 1; q_fire.push({ ny,nx }); } } } int result = 0; queueq_sg; q_sg.push({ yst,xst }); sg_time[yst][xst] = 0; while (!q_sg.empty()) { Node now = q_sg.front(); q_sg.pop(); if (now.y == 0 || now.x == 0 || now.y == N - 1 || now.x == M - 1) { result = sg_time[now.y][now.x] + 1; break; } for (int i = 0; i < 4; i++) { int ny = now.y + dr[i]; int nx = now.x+ dc[i]; if (board[ny][nx] == '#')continue; if (!isValid(ny, nx))continue; if (sg_time[ny][nx] != -1)continue; if (sg_time[now.y][now.x] + 1 >= fire_time[ny][nx])continue; sg_time[ny][nx] = sg_time[now.y][now.x] + 1; q_sg.push({ ny,nx }); } } if (result == 0) { cout << "IMPOSSIBLE" << '\n'; } else { cout << result << '\n'; } } }

제출 #122508

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: