#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 while(!escape_q.empty()) { point offset = escape_q.front(); escape_q.pop(); //exception if(row-1 == offset.y || 0 == offset.y || col-1 == offset.x || 0 == offset.x )return 1; visit[offset.y][offset.x] = offset.cnt; 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)return dcnt; visit[dy][dx] = dcnt; escape_q.push({dy,dx,dcnt}); } } } } } 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]) { fire_q.push({j,k,1}); visit[j][k] = 1; } else if('@' == map[j][k]) { escape_q.push({j,k,1}); } } } 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; }

제출 #12533

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: