[BOJ-4179]불!

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

시작위치(1개), 불의 위치가 주어진다 이때 주어진 지도의 끝까지 도달하여 탈출 할 수 있을 때 가장 빠른 탈출 시간을 출력한다. 

만약 탈출할 수 없다면 "IMPOSSIBLE" 을 출력한다. 

벽으로는 이동할 수 없고, 움직이는 위치에 불이 있으면 이동할 수 없다. 그리고 상하좌우 4방향으로 이동이 가능하다.

불은 벽으로 이동할 수 없고, 상하좌우 4방향으로 퍼진다.

[접근방법]

BFS 로 문제를 풀이하였다.

먼저 사람위치부터 이동을 시킨 후, 같은 시간대에 모든 움직임이 끝났다면, 불을 이동시킨다.

불 또한 같은 시간대에 이동을 마친 후, 사람이 끝에 도달한 적이 있는지 확인한다. 

이 과정을 반복해서 풀이하였다.

[C++11 source code BFS]

#include<cstdio>
#include<queue>
#include<memory.h>
using namespace std;
const int M = 1111;
const int INF = 1 << 20;
const int FIRE = 1 << 22;
const int dr[] = { 0,0,1,-1 };
const int dc[] = { 1,-1,0,0 };
int vis[M][M];
char im[M][M];
int ROW, COL;
 
struct pos {
    int r;
    int c;
    int mov;
    pos() {}
    pos(int ir, int ic, int im) :r(ir), c(ic), mov(im) {}
    void set_pos(int ir, int ic, int im) { r = ir; c = ic; mov = im; }
};
 
int main() {
    scanf("%d%d", &ROW, &COL);
    queue<pos> F;
    queue<pos> J;
 
    for (int r = 0; r < ROW; r++) {
        scanf("%s", im[r]);
        for (int c = 0; c < COL; c++) {
            vis[r][c] = INF;
            if (im[r][c] == 'J') {
                vis[r][c] = 1;
                J.push(pos(r, c, 1));
                if (r == 0 || r == ROW - 1 || c == 0 || c == COL - 1) {
                    puts("1");
                    return 0;
                }
            }
            else if (im[r][c] == 'F') {
                F.push(pos(r, c, 1));
                vis[r][c] = FIRE;
            }
            else if (im[r][c] == '#') {
                vis[r][c] = INF + 5;
            }
        }
    }
 
 
    int mov = 1;
    bool ok = false;
    int ans = INF;
    while (!J.empty()) {
        pos here = J.front(); J.pop();
 
        if (here.mov > mov) {
            while (!F.empty()) {
                pos there = F.front(); F.pop();
 
                if (there.mov > mov) {
                    F.push(pos(there));
                    break;
                }
 
                for (int i = 0; i < 4; i++) {
                    int tr = there.r + dr[i];
                    int tc = there.c + dc[i];
 
                    if (tr < 0 || ROW <= tr || tc < 0 || COL <= tc) continue;
                    if (im[tr][tc] == 'F') continue; // fire
                    if (im[tr][tc] == '#') continue; // wall
 
                    vis[tr][tc] = FIRE;
                    im[tr][tc] = 'F';
                    F.push(pos(tr, tc, there.mov + 1));
                }
            }
            mov++;
            for (int r = 0; r < ROW; r++) {
 
                for (int c = 0; c < COL; c++) {
                    if (0 < r && r < ROW - 1 && 0 < c && c < COL - 1) continue;
                    ans = (ans > vis[r][c]) ? vis[r][c] : ans;
                }
            } // check
            if (ans < INF) break;
 
            /*puts("");
            for (int r = 0; r < ROW; r++) {
            for (int c = 0; c < COL; c++) {
            printf("%c", im[r][c]);
            }
            puts("");
            }*/
        } // F move
 
        if (vis[here.r][here.c] == FIRE) continue;
 
        for (int i = 0; i < 4; i++) {
            int tr = here.r + dr[i];
            int tc = here.c + dc[i];
 
            if (tr < 0 || ROW <= tr || tc < 0 || COL <= tc) continue;
            if (im[tr][tc] == 'F') continue; // fire
            if (im[tr][tc] == '#') continue; // wall
 
            if (vis[tr][tc] == INF) {
                vis[tr][tc] = here.mov + 1;
                im[tr][tc] = 'J';
                J.push(pos(tr, tc, here.mov + 1));
            }
        } // J move
    }
 
    //puts("");
    //for (int r = 0; r < ROW; r++) {
    //    for (int c = 0; c < COL; c++) {
    //        printf("%c", im[r][c]);
    //    }
    //    puts("");
    //}
 
    if (ans == INF) puts("IMPOSSIBLE");
    else printf("%d\n", ans); // or ans+1
 
    return 0;
}