BOJ)5427 불

문제: icpc.me/5427

가중치가 없는 그래프에서의 최단경로 이므로 BFS를 이용하여 문제를 해결해준다.

 단 불이라는 새로운 조건이 존재하는데 우리는 queue에 상근이와 불을 동시에 삽입해주어 불일 경우와 상근이일 경우를 다르게 처리해주면 된다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int t, w, h, sx, sy;
char a[1001][1001];
int disc[1001][1001], fire[1001][1001];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
bool chk(int x, int y) {
    return 0 <= x&&x < w && 0 <= y&&y < h;
}
bool out(int x, int y) {
    return 0 == x || x == w - 1 || y == 0 || y == h - 1;
}
int bfs() {
    queue<pair<pair<int, int>, int>> qu;
    int day = 0;
    qu.push({ { sx,sy },1 });
    disc[sx][sy] = 1;
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < h; j++)
            if (fire[i][j]) {
                disc[i][j] = 2;
                qu.push({ {i,j},2 });
            }
    }
    while (qu.size()) {
        int qs = qu.size();
        while (qs--) {
            int hx = qu.front().first.first;
            int hy = qu.front().first.second;
            int hz = qu.front().second;
            qu.pop();
            if (disc[hx][hy] == 1 && out(hx, hy))
                return day + 1;
            for (int i = 0; i < 4; i++) {
                int cx = hx + dx[i];
                int cy = hy + dy[i];
                if (hz == 1) {
                    if (chk(cx, cy) && disc[cx][cy]<hz && a[cx][cy] == '.') {
                        disc[cx][cy] = hz;
                        qu.push({ { cx,cy },hz });
                    }
                }
                else {
                    if (chk(cx, cy) && disc[cx][cy]<hz && a[cx][cy] != '#') {
                        disc[cx][cy] = hz;
                        qu.push({ { cx,cy },hz });
                    }
                }
            }
        }
        day++;
    }
    return -1;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &h, &w);
        memset(disc, 0, sizeof(disc));
        memset(fire, 0, sizeof(fire));
        for (int i = 0; i < w; i++) {
            getchar();
            for (int j = 0; j < h; j++) {
                scanf("%c", &a[i][j]);
                if (a[i][j] == '@') {
                    sx = i;
                    sy = j;
                }
                else if (a[i][j] == '*')
                    fire[i][j] = 1;
            }
        }
        int ret = bfs();
        if (ret == -1)
            puts("IMPOSSIBLE");
        else
            printf("%d\n", ret);
    }
    return 0;
}