[백준 4179] 불!

백준 4179 불!

 

 

이 문제는 불이랑 거의 같은 문제라고 볼 수 있다.(이 문제를 풀면서 다시 처음부터 짰기 때문에 풀이는 살짝 느낌이 다를 것이다. 불이랑 다른건 상근(@)이가 아니라 지훈(J)이로 바뀌었고 불(*)은 불(F)로 바뀌었다. 

풀이는 이전 포스트에서 간단히 설명을 올렸으니 저 곳에서 한번 보면 될 것이다.

#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>
 
using namespace std;
 
queue<pair<int, int>> q;
queue<pair<int, int>> fire;
char vmap[1001][1001] = { 0 };
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", vmap[i]);
        for (int j = 0; j < m; j++)
        {
            if (vmap[i][j] == 'F')fire.push(make_pair(i, j));
            if (vmap[i][j] == 'J')q.push(make_pair(i, j));
        }
    }
    int ans = 0;
    int qsize, firesize;
    while (1) {
        ans++;
        firesize = fire.size();
        while (firesize--)
        {
            pair<int, int> now = fire.front(); fire.pop();
 
            for (int k = 0; k < 4; k++)
            {
                int qx = now.second + dx[k];
                int qy = now.first + dy[k];
 
                if (vmap[qy][qx] == '.' || vmap[qy][qx] == 'J')
                {
                    vmap[qy][qx] = 'F';
                    fire.push(make_pair(qy, qx));
                }
            }
        }
 
        qsize = q.size();
        while (qsize--) {
            pair<int, int> now = q.front(); q.pop();
 
            for (int k = 0; k < 4; k++)
            {
                int qx = now.second + dx[k];
                int qy = now.first + dy[k];
 
                if (qx < 0 || qx >= m || qy < 0 || qy >= n)return printf("%d", ans) * 0;
                if (vmap[qy][qx] == '.')
                {
                    vmap[qy][qx] = 'J';
                    q.push(make_pair(qy, qx));
                }
            }
        }
        qsize = q.size();
        
        if (qsize == 0)return printf("IMPOSSIBLE") * 0;
    }
 
}