#include #define X first #define Y second using namespace std; char board[1001][1001]; int dist1[1001][1001]; int dist2[1001][1001]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n, m; // n,m <= 1,000 cin >> m >> n; bool flag = 0; queue> Q1; queue> Q2; for(int i=0; i> str; for(int j=0; j cur = Q1.front(); Q1.pop(); for(int i=0; i<4; i++) { int nx = cur.X + dx[i]; int ny = cur.Y + dy[i]; if(nx<0 || ny<0 || nx>=n || ny>=m) continue; if(board[nx][ny] == '#' || dist1[nx][ny] >= 0) continue; dist1[nx][ny] = dist1[cur.X][cur.Y]+1; Q1.push({nx, ny}); } } while(!Q2.empty()) { pair cur = Q2.front(); Q2.pop(); for(int i=0; i<4; i++) { int nx = cur.X + dx[i]; int ny = cur.Y + dy[i]; if(nx<0 || ny<0 || nx>=n || ny>=m) { cout << dist2[cur.X][cur.Y]+1 << '\n'; flag = 1; } if(board[nx][ny] == '#' || dist2[nx][ny] >= 0) continue; if(dist1[nx][ny] <= dist2[cur.X][cur.Y]+1 && dist1[nx][ny] != -1) continue; dist2[nx][ny] = dist2[cur.X][cur.Y]+1; Q2.push({nx, ny}); } } if(!flag) cout << "IMPOSSIBLE\n"; } return 0; }

제출 #15905

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: