#include #include #include #include #include using namespace std; int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1}; int visited_f[1001][1001],visited_s[1001][1001]; int main() { int T,w,h; cin >> T; for(int i = 0; i < T; i++) { int ans = 0; cin >> w >> h; for(int i = 0; i < h;i++) { fill(visited_f[i],visited_f[i]+w,0); fill(visited_s[i],visited_s[i]+w,0); } queue> Q_f,Q_s; for(int i = 0; i < h; i++) { string tmp; cin >> tmp; for(int j = 0; j < w; j++) { if(tmp[j] == '.') continue; else if(tmp[j] == '#') { visited_f[i][j] = -1; visited_s[i][j] = -1; } else if(tmp[j] == '*') { visited_f[i][j] = 1; Q_f.push({i,j}); } else { visited_s[i][j] = 1; Q_s.push({i,j}); } } } while(!Q_f.empty()) { int curX = Q_f.front().first; int curY = Q_f.front().second; Q_f.pop(); for(int i = 0; i < 4; i++) { int nx = curX + dx[i]; int ny = curY + dy[i]; if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue; if(visited_f[nx][ny] == -1 || visited_f[nx][ny] > 0) continue; Q_f.push({nx,ny}); visited_f[nx][ny] = visited_f[curX][curY] + 1; } } while(!Q_s.empty()) { int curX = Q_s.front().first; int curY = Q_s.front().second; Q_s.pop(); for(int i = 0; i < 4; i++) { int nx = curX + dx[i]; int ny = curY + dy[i]; if(nx < 0 || nx >= h || ny < 0 || ny >= w) { ans = visited_s[curX][curY]; break; } if(visited_s[nx][ny] == -1) continue; if(visited_f[nx][ny] != 0 && visited_f[nx][ny] <= visited_s[curX][curY]+1) continue; Q_s.push({nx,ny}); visited_s[nx][ny] = visited_s[curX][curY] + 1; } if(ans != 0) break; } if(ans!=0) { cout << ans << "\n"; } else { cout << "IMPOSSIBLE" << "\n"; } } return 0; }

제출 #10978

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: