[알고리즘] 백준 5427 - 불 (C++)

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

#include <iostream>
#include <queue>
using namespace std;

int T, W, H;
char Arr[1001][1001];
queue<pair<int, int>> S, Q;
int Dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void setting(){
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            Arr[i][j] = '.';
        }
    }
    while(S.empty() == false){
        S.pop();
    }
    while(Q.empty() == false){
        Q.pop();
    }
    return;
}

int solve(){
    int ret = 0;
    while(S.empty() == false){
        ret++;

        int tmp = Q.size();
        for(int i=0; i<tmp; i++){
            int y = Q.front().first;
            int x = Q.front().second;
            Q.pop();

            for(int d=0; d<4; d++){
                int ny = y + Dir[d][0];
                int nx = x + Dir[d][1];

                if(ny < 0 || ny >= H || nx < 0 || nx >= W){
                    continue;
                }
                if(Arr[ny][nx] != '.'){
                    continue;
                }

                Arr[ny][nx] = '*';
                Q.push({ny, nx});
            }
        }

        int cnt = S.size();
        for(int i=0; i<cnt; i++){
            int y = S.front().first;
            int x = S.front().second;
            S.pop();

            for(int d=0; d<4; d++){
                int ny = y + Dir[d][0];
                int nx = x + Dir[d][1];

                if(ny < 0 || ny >= H || nx < 0 || nx >= W){
                    return ret;
                }
                if(Arr[ny][nx] != '.'){
                    continue;
                }

                Arr[ny][nx] = '@';
                S.push({ny, nx});
            }
        }
    }
    return -1;
}

int main(){
    cin >> T;
    while(T--){
        setting();

        cin >> W >> H;
        for(int i=0; i<H; i++){
            for(int j=0; j<W; j++){
                cin >> Arr[i][j];
                if(Arr[i][j] == '@'){
                    S.push({i, j});
                }
                else if(Arr[i][j] == '*'){
                    Q.push({i, j});
                }
            }
        }

        int cnt = solve();
        if(cnt == -1){
            cout << "IMPOSSIBLE\n";
        }
        else{
            cout << cnt << "\n";
        }
    }
    return 0;
}