[C++] 백준 4179번: 불!

좀 까다로운 문제였는데, 언제든지 응용해서 나올 수 있을 것 같은 느낌을 받았다.

탈출을 하기 위해서는 nx, ny가 0이나 n, m 크기를 넘어가야했다. 반복을 돌리다가 넘어간 경우 현재의 dist에서 1을 더해 출력해주었다.

 또한 불의 dist와 J의 dist를 비교하여 불의 dist가 더 낮은 경우 이미 불이 빠르게 도착한 상태이므로, continue를 통해 다음 큐로 넘어갈 수 있도록 했다.

 

#include <iostream>
#include <queue>
#define X first
#define Y second
using namespace std;

int n, m;
string board[1002];
int distF[1002][1002];
int distJ[1002][1002];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> board[i];
    }
    for(int i = 0; i < n; i++){
        fill(distF[i], distF[i] + m, -1);
        fill(distJ[i], distJ[i] + m, -1);
    }
    
    queue <pair<int, int>> QF;
    queue <pair<int, int>> QJ;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(board[i][j] == 'F'){
                QF.push({i, j});
                distF[i][j] = 0;
            }
            if(board[i][j] == 'J'){
                QJ.push({i, j});
                distJ[i][j] = 0;
            }
        }
    }
    
    while(!QF.empty()){
        auto cur = QF.front(); QF.pop();
        for(int i = 0; i < 4; i++){
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(distF[nx][ny] >= 0 || board[nx][ny] == '#') continue;
            QF.push({nx, ny});
            distF[nx][ny] = distF[cur.X][cur.Y] + 1;
        }
    }
    
    while(!QJ.empty()){
        auto cur = QJ.front(); QJ.pop();
        for(int i = 0; i < 4; i++){
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) {
                cout << distJ[cur.X][cur.Y] + 1;
                return 0;
            }
            if(distJ[nx][ny] >= 0 || board[nx][ny] == '#') continue;
            if(distF[nx][ny] >= 0 && distF[nx][ny] <= distJ[cur.X][cur.Y] + 1) continue;
            QJ.push({nx, ny});
            distJ[nx][ny] = distJ[cur.X][cur.Y] + 1;
        }
    }
    cout << "IMPOSSIBLE";
    
    return 0;
}