#include #include #include using namespace std; struct point { int y; int x; int cnt; }; char map[1000][1000]; int visit[1000][1000]; int direct[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}}; queuefire_q; queueescape_q; int bfs(const int col, const int row) { // flood fill fire while(!fire_q.empty()) { point offset = fire_q.front(); fire_q.pop(); for(int i=0; i<4; ++i) { int dy = offset.y + direct[i][0]; int dx = offset.x + direct[i][1]; int dcnt = offset.cnt + 1; if(!(dy >= row || dy<0 || dx>=col || dx<0)) { if('.' == map[dy][dx] || '@' == map[dy][dx]) { if(!visit[dy][dx] || dcnt < visit[dy][dx]) { visit[dy][dx] = dcnt; fire_q.push({dy,dx,dcnt}); } } } } } //flood fill - escape_q int ans = 21e8; // if escape_q is not empty , min value record bool escape_flag = false; point st = escape_q.front(); visit[st.y][st.x] = 1; while(!escape_q.empty()) { point offset = escape_q.front(); escape_q.pop(); for(int i=0; i<4; ++i) { int dy = offset.y + direct[i][0]; int dx = offset.x + direct[i][1]; int dcnt = offset.cnt + 1; if(!(dy >= row || dy<0 || dx>=col || dx<0)) { if('.' == map[dy][dx]) { if(!visit[dy][dx] || dcnt < visit[dy][dx]) { if(row-1 == dy || 0 == dy || col-1 == dx || 0 == dx) { if(ans > dcnt) ans = dcnt; escape_flag = true; } visit[dy][dx] = dcnt; escape_q.push({dy,dx,dcnt}); } } } } } if(escape_flag) { return ans; } else return 0; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); int T,W,H; cin >> T; for(int i=0; i> W >> H; // map assign for(int j=0; j> map[j][k]; if('@' == map[j][k]) { if(0 == j || H-1 == j || W-1 == k || 0 == k) { cout << 1; flag = true; break; } else escape_q.push({j,k,1}); } if('*' == map[j][k]) { fire_q.push({j,k,1}); visit[j][k] = 1; } } if(flag)break; } if (flag) { if (1 != T) { for (int j = 0; j < H; ++j) { while(!fire_q.empty())fire_q.pop(); memset(visit[j], 0, sizeof(int) * W); } } cout << 1 << "\n"; continue; } else { int ret = bfs(W, H); if (ret) { cout << ret << "\n"; } else cout << "IMPOSSIBLE" << "\n"; } if(1 != T) { for (int j = 0; j < H; ++j) { memset(visit[j], 0, sizeof(int) * W); } } } return 0; }

제출 #12597

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: