[백준] 4179 - 불! (C++)

1. 문제 소개 

 

2. 해결 방안과 알고리즘 

 

BFS로 최단거리를 계산할 수 있다. 근데 불이랑 지훈이의 움직임을 둘 다 계산해야 한다. 

 

 

만약에 fire가 먼저, 지훈이가 지나가야 할 특정 칸에 닿으면(즉, 기록하는 숫자가 fire < 지훈) 이면 탈출하지 못한다 

 

3. 코드 

#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

string board[1002];
int fire[1002][1002];
int escape[1002][1002];

queue<pair<int, int>> qf;
queue<pair<int, int>> qe;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int R, C;
    cin >> R >> C;

    for (int i =0; i<R; i++){
        fill(fire[i], fire[i]+C, -1);
        fill(escape[i], escape[i]+C, -1);
        cin >> board[i];
    }


    for (int i=0; i<R; i++){
        for (int j=0; j<C; j++){
            if (board[i][j] == 'F'){
                qf.push({i, j});
                fire[i][j] = 0;
            }
            if (board[i][j] == 'J'){
                qe.push({i,j});
                escape[i][j] = 0;
            }
        }
    }


    while (!qf.empty())
    {
        pair<int, int> cur = qf.front();
        qf.pop();
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (nx < 0 || nx >= R || ny < 0 || ny >= C)
                continue;
            if (fire[nx][ny] >= 0 || board[nx][ny] == '#')
                continue;
            fire[nx][ny] = fire[cur.first][cur.second] + 1;
            qf.push({nx, ny});
        }
    }


    while (!qe.empty())
    {
        pair<int, int> cur = qe.front();
        qe.pop();
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (nx < 0 || nx >= R || ny < 0 || ny >= C){
                cout << escape[cur.first][cur.second] + 1;
                return 0;}
            if (escape[nx][ny] >= 0 || board[nx][ny] == '#') continue;
            if (fire[nx][ny] != -1 && fire[nx][ny] <= escape[cur.first][cur.second] +1 )
                continue;
            escape[nx][ny] = escape[cur.first][cur.second] + 1;
            qe.push({nx, ny});
        }
    }

    cout << "IMPOSSIBLE" << endl;
}