5427번: 불

https://www.acmicpc.net/problem/5427


$O(thw)$

불->상근->불->상근...
순으로 bfs를 돌려 탈출할 수 있는지 확인한다.

#include<cstdio>
#include<queue>
using namespace std;
const int fx[] = { 1,0,-1,0 }, fy[] = { 0,1,0,-1 };
struct st { int x, y, c; };
int t, w, h;
char s[1000][1001];
int main() {
    for (scanf("%d", &t); t--;) {
        int ck[1000][1001] = { 0, }, tx, ty;
        queue<st> q;
        scanf("%d%d", &w, &h);
        for (int i = 0; i < h; i++) {
            scanf("%s", s[i]);
            for (int j = 0; j<w; j++) if (s[i][j] == '*') ck[i][j] = 1, q.push({ i,j,0 });
            else if (s[i][j] == '@') tx = i, ty = j;
        }
        ck[tx][ty] = 1; q.push({ tx,ty,1 });
        while (!q.empty()) {
            st p = q.front();
            if ((!p.x || !p.y || p.x == h - 1 || p.y == w - 1) && p.c) { printf("%d\n", ck[p.x][p.y]); break; }
            for (int i = 0; i < 4; i++) {
                tx = p.x + fx[i]; ty = p.y + fy[i];
                if (tx < 0 || ty < 0 || tx == h || ty == w || ck[tx][ty] || s[tx][ty] == '#') continue;
                ck[tx][ty] = ck[p.x][p.y] + 1;
                q.push({ tx,ty,p.c });
            }
            q.pop();
        }
        if (q.empty()) puts("IMPOSSIBLE");
    }
    return 0;
}