4190 - 불!

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

4179번: 불!

생각해 보기

1. 지훈이는 불에 타기전에 탈출을 하며, 불이 붙은 위치를 감안해서 탈출한다고 한다.

2. 불을 먼저 움직이고 지훈이를 움직이자.

3. 불은 여러개가 붙어 있을 수 있으니 리스트나 큐로 저장하자.

4. 가장자리에 도착했다고 탈출이 아니다! 벗어나는 경우를 위해 가장자리 도착 + 1을 해주자

 

코드

#include<iostream>
#include<queue>

using namespace std;

int R,C;
char arr[1001][1001];
int my[4] = {0,1,0,-1};
int mx[4] = {1,0,-1,0};
bool chk[1001][1001];
queue<pair<int, int> > q, fq;

void input(){
    cin>>R>>C;

    for(int i=0;i<R;++i){
        for(int j=0;j<C;++j){
            cin>>arr[i][j];
            if(arr[i][j]=='J'){
                q.push({i,j});
                chk[i][j]=true;
                arr[i][j]='.';
            }
            else if(arr[i][j]=='F'){
                fq.push({i,j});
            }
        }
    }
}

void spread(){
    queue<pair<int, int> > tq;

    while(!fq.empty()){
        int y = fq.front().first;
        int x = fq.front().second;

        fq.pop();
        
        for(int i=0;i<4;++i){
            int ny = y + my[i];
            int nx = x + mx[i];

            if(y<0||x<0||x>=C||y>=R||arr[ny][nx]!='.')
                continue;

            arr[ny][nx]='F';
            tq.push({ny,nx});
        }
    }

    fq = tq;
}

bool bfs(){
    queue<pair<int, int> > tq;

    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        if(y<=0||x<=0||x>=C-1||y>=R-1)
            return true;

        for(int i=0;i<4;++i){
            int ny = y + my[i];
            int nx = x + mx[i];

            if(y<0||x<0||x>=C||y>=R||arr[ny][nx]!='.'||chk[ny][nx])
                continue;

            chk[ny][nx]=true;
            tq.push({ny,nx});
        }
    }

    q = tq;
    return false;
}

void solution(){
    int cnt = 0;
    
    while(!q.empty()){
        spread();
        if(bfs()){
            cout<<cnt+1<<'\n';
            return;
        }
        ++cnt;
    }
    cout<<"IMPOSSIBLE"<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solution();

    return 0;
}