#include #include #include #include #include using namespace std; int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; int start_x, start_y; vector> Building; deque> Fires; int main(){ int TC; cin >> TC; for(int tc = 0; tc < TC; tc++){ int w, h; cin >> w >> h; Building.resize(h, vector(w, 0)); for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ char c; cin >> c; if(c == '#'){ Building[i][j] = -1; }else if(c == '*'){ Fires.push_back({i, j, 1}); Building[i][j] = 1; }else if(c == '@'){ start_x = i; start_y = j; } } } while(!Fires.empty()){ int px, py, pt; tie(px, py, pt) = Fires.front(); Fires.pop_front(); for(int i = 0; i < 4; i++){ int nx = px + dx[i]; int ny = py + dy[i]; if(0 <= nx && nx < h && 0 <= ny && ny < w){ int New = Building[nx][ny]; if(New != -1 && (New == 0 || New > pt + 1)){ Building[nx][ny] = pt + 1; Fires.push_back({nx, ny, pt + 1}); } } } } // for(int i = 0; i < h; i++){ // for(int j = 0; j < w; j++){ // cout << Building[i][j] << " "; // } // cout << "\n"; // } bool escape = false; int escapetime = 1e9; if(Building[start_x][start_y] > 1){ Building[start_x][start_y] = 1; deque> dq; dq.push_back({start_x, start_y, 1}); while(!dq.empty()){ int px, py, pt; tie(px, py, pt) = dq.front(); if(px == 0 || px == h - 1 || py == 0 || py == w - 1){ escape = true; escapetime = min(pt, escapetime); } dq.pop_front(); for(int i = 0; i < 4; i++){ int nx = px + dx[i]; int ny = py + dy[i]; if(0 <= nx && nx < h && 0 <= ny && ny < w && Building[nx][ny] != -1 && Building[nx][ny] > pt + 1){ Building[nx][ny] = pt + 1; dq.push_back({nx, ny, pt + 1}); } } } dq.clear(); } if(escape){ cout << escapetime << "\n"; }else{ cout << "IMPOSSIBLE\n"; } Building.clear(); Fires.clear(); } return 0; }

제출 #122544

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: