#include #define ll long long #define endl '\n' #define all(x) (x).begin(), (x).end() #define vi vector #define vvi vector #define vb vector #define vvb vector #define pii pair #define loop(i, s, n) for (int i = s; i < n; i++) #define X first #define Y second using namespace std; int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1}; int N, R, C; queue fires; vector> matrix; short dist[1001][1001]; void progress_fire() { int fsize = fires.size(); loop (f, 0, fsize) { auto [fi, fj] = fires.front(); fires.pop(); // 왜 queue로 써도 무방한가? -> 이미 퍼진 불만 care해도 되기 때문 loop(d, 0, 4) { int ni = fi + di[d], nj = fj + dj[d]; if (ni >= 0 && nj >= 0 && ni < R && nj < C && matrix[ni][nj] == '.') { matrix[ni][nj] = '*'; fires.emplace(ni, nj); } } } } int ans(pii start) { queue queue; queue.emplace(start); dist[start.X][start.Y] = 1; while (!queue.empty()) { int size = queue.size(); loop(_, 0, size) { auto [i, j] = queue.front(); queue.pop(); loop(d, 0, 4) { int ni = i + di[d], nj = j + dj[d]; if (ni >= 0 && nj >= 0 && ni < R && nj < C && matrix[ni][nj] == '.') { if (dist[ni][nj] == 0) { dist[ni][nj] = dist[i][j] + 1; if (ni == 0 || nj == 0 || ni == R - 1 || nj == C - 1) return dist[ni][nj]; queue.emplace(ni, nj); } } } } progress_fire(); } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N; while (N--){ cin >> C >> R; matrix = vector>(R, vector(C)); memset(dist, 0, sizeof(dist)); pii start; loop(i, 0, R) loop(j, 0, C) { cin >> matrix[i][j]; if (matrix[i][j] == '@') { start = {i, j}; matrix[i][j] = '.'; } if (matrix[i][j] == '*') fires.emplace(i, j); } int answer = ans(start); if (answer == -1) cout << "IMPOSSIBLE" << endl; else cout << answer << endl; } }

제출 #40396

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: