#include using namespace std; int T; vector dy = { -1, 0, 1, 0 }; vector dx = { 0, 1, 0, -1 }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed; cin >> T; while (T--) { int N, M; cin >> M >> N; vector> board(N, vector(M)); vector> visited(N, vector(M, false)); pair pos; queue> q; for (int i = 0; i < N; i++) { string str; cin >> str; for (int j = 0; j < M; j++) { board[i][j] = str[j]; if (board[i][j] == '@') { pos = { i, j }; } if (board[i][j] == '*') { q.push({ i,j }); } } } queue> player; player.push(pos); visited[pos.first][pos.second] = true; if (q.empty()) { int cnt = 0; bool flag = false; while (!player.empty()) { int size = player.size(); for (int p = 0; p < size; p++) { auto [y, x] = player.front(); player.pop(); for (int i = 0; i < 4; i++) { int newY = y + dy[i]; int newX = x + dx[i]; if (newY < 0 || newY >= N || newX < 0 || newX >= M) { //탈출 cout << cnt + 1 << "\n"; flag = true; break; } if (board[newY][newX] == '*' || board[newY][newX] == '#') continue; if (visited[newY][newX]) continue; visited[newY][newX] = true; player.push({ newY, newX }); } if (flag) break; } if (flag) break; cnt++; } continue; } int cnt = 0; bool flag = false; while (!q.empty()) { int size = q.size(); for (int t = 0; t < size; t++) { auto [y, x] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int newY = y + dy[i]; int newX = x + dx[i]; if (newY < 0 || newY >= N || newX < 0 || newX >= M) continue; if (board[newY][newX] == '*' || board[newY][newX] == '#') continue; board[newY][newX] = '*'; q.push({ newY, newX }); } } int playerSize = player.size(); for(int p = 0 ; p < playerSize; p++) { auto [y, x] = player.front(); player.pop(); for (int i = 0; i < 4; i++) { int newY = y + dy[i]; int newX = x + dx[i]; if (newY < 0 || newY >= N || newX < 0 || newX >= M) { //탈출 cout << cnt + 1 << "\n"; flag = true; break; } if (board[newY][newX] == '*' || board[newY][newX] == '#') continue; if (visited[newY][newX]) continue; visited[newY][newX] = true; player.push({ newY, newX }); } if (flag) break; } if (flag) break; cnt++; } if (!flag) cout << "IMPOSSIBLE\n"; } return 0; }

제출 #16541

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: