Q4179.md

Q4179

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• # : 벽
• . : 지나갈 수 있는 공간
• J : 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F : 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int r, c;
    cin >> r >> c;
    string str[1002];
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
    queue<pair<int, int>> exodus;
    queue<pair<int, int>> fire;
    int fDist[1002][1002];
    int jDist[1002][1002];
    for(int i=0;i<r;i++) {
        fill(fDist[i], fDist[i]+c, -1);
        fill(jDist[i], jDist[i]+c, -1);
    }
    for(int i=0;i<r;i++) cin >> str[i];

    for(int i=0;i<r;i++) {
        for(int j=0;j<c;j++){
            if(str[i][j] == 'J') {
                exodus.push({i, j});
                jDist[i][j] = 0;
            }
            if(str[i][j] == 'F') { 
                fire.push({i, j});
                fDist[i][j] = 0;
            }
        }
    }

    while(!fire.empty()) {
        pair<int, int> curF = fire.front();
        fire.pop();
        for(int i=0;i<4;i++) {
            int fx = curF.first + dx[i];
            int fy = curF.second + dy[i];
            // 불 움직이기
            // 1) 불이 가지 못하는 곳
            if(fx < 0 || fx >= r || fy < 0 || fy >=c) continue;
            // 벽이거나 이미 갔던 곳
            if(str[fx][fy] == '#' || fDist[fx][fy] >=0) continue;
            fDist[fx][fy] = fDist[curF.first][curF.second] + 1;
            fire.push({fx, fy});
        }
    }
    while(!exodus.empty()) {
        pair<int, int> curJ = exodus.front();
        exodus.pop(); 
        for(int i=0;i<4;i++) {
            int jx = curJ.first + dx[i];
            int jy = curJ.second + dy[i];
            if(jx < 0 || jx >= r || jy < 0 || jy >=c) {
                cout << jDist[curJ.first][curJ.second] + 1;
                return 0;
            }
            // 지훈이 움직이기
            // 1) 지훈이가 가지 못하는 곳
            if(str[jx][jy] == '#' || jDist[jx][jy] >= 0) continue;
            // 이미 fire가 다녀간 곳이거나, 도착한 시점에 불이 동시에 도착하거나, 혹은 자신보다 불이 더 빨리 도착하는 자리에 갈 수 없음.
            if(fDist[jx][jy]!=-1 && fDist[jx][jy] <= jDist[curJ.first][curJ.second]+1) continue;
            jDist[jx][jy] = jDist[curJ.first][curJ.second] + 1;
            exodus.push({jx, jy});
        }
    }
    cout << "IMPOSSIBLE";
    return 0;
}