[백준 5427번] 불

문제 링크: https://www.acmicpc.net/problem/5427

5427번: 불

<문제 풀이> BFS

이 문제는 4179번 문제에서 테스트 케이스가 추가된 문제입니다.

각 테스트 케이스마다 배열을 초기화하는 작업만 추가하면 됩니다.

https://seokjin2.tistory.com/67

[백준 4179번] 불!

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first
#define Y second
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1 , 0, -1, 0 };
 
char board[1000][1000];
int fire[1000][1000];
int person[1000][1000];
int w, h;
void f_bfs() {
    queue<pair<int, int> >Q;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (board[i][j] == '*') {
                Q.push({ i, j });
                fire[i][j] = 1;
            }
        }
    }
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || ny < 0 || nx >= h || ny >= w)continue;
            if (board[nx][ny] == '#' || fire[nx][ny])continue;
            fire[nx][ny] = fire[cur.X][cur.Y] + 1;
            Q.push({ nx, ny });
        }
    }
}
int p_bfs() {
    f_bfs();
    queue<pair<int, int> >Q;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (board[i][j] == '@') {
                Q.push({ i, j });
                person[i][j] = 1;
            }
        }
    }
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || ny < 0 || nx >= h || ny >= w) { // 탈출 성공
                return person[cur.X][cur.Y];
            }
            if (board[nx][ny] == '#' || (person[cur.X][cur.Y] + 1 >= fire[nx][ny] && fire[nx][ny])  || person[nx][ny])continue; //벽 또는 불 때문에 이동 못하는 경우
            person[nx][ny] = person[cur.X][cur.Y] + 1;
            Q.push({ nx, ny });
        }
    }
    return 0; // 탈출 실패
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_case; cin >> test_case;
    while (test_case--) {
        cin >> w >> h;
        for (int i = 0; i < h; i++) {
            string s; cin >> s;
            for (int j = 0; j < w; j++) {
                board[i][j] = s[j];
            }
        }
        int res = p_bfs();
        if (res) cout << res << '\n';
        else cout << "IMPOSSIBLE\n";
 
        fill(&fire[0][0], &fire[999][1000], 0);
        fill(&person[0][0], &person[999][1000], 0);
 
    }
    return 0;
}