boj:4199ドル!

ソース:https://www.acmicpc.net/problem/4179
質問する
志訓は迷宮で働いている.智勲を助けて迷宮を脱出せよ!
智勲の迷路での位置と点火された位置を考慮して、智勲が火に焼かれる前に脱出できるかどうか、そしてどれだけ速いスピードで脱出できるかを決めなければならない.
智勲と火は毎分水平または垂直に1格移動する(傾斜せずに移動する).
火は各点から4方向に拡散する.
ジフンは迷宮の端に近い空間から脱出できる.
智勲と火は壁のある空間を通ることができない.
入力
入力された最初の行には、スペースで区切られた2つの整数RとCが与えられます.ただし,1≦R,C≦1000であった.Rは迷宮行の個数,Cは列の個数である.
次の入力では、R行にそれぞれ迷路行が与えられる.
各文字の意味は次のとおりです.

#:壁

.: 通過可能空間

J:ジフンの迷宮での初期位置(通過可能な空間)

F:発火空間

Jは入力に1つしか与えられていない.

しゅつりょく
智勲が火が到着するまで迷宮を脱出できなければ、IMPOSIBLEを出力する.
智勲が迷宮から脱出できれば、最も速い脱出時間を出力する.
アクセス時の配列は2種類あります.
火事の空間は智勲が通り抜けられない場所を考慮しなければならない.
智勲も火のbfsも回ってくれればいいのに、智勲の場合、迷路を離れると、逃げた部分を条件にして、繰り返し文の条件を入れて完成させ、条件が満たさなければ、繰り返し文が終わると逃げられないので、出力は不可能です.
コードから見ると、以下のようになります.

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

string board[1002];
int vis1[1002][1002];
int vis2[1002][1002];
int n,m;

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

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m;
    for(int i=0; i<n; i++)
    {
        fill(vis1[i], vis1[i]+m, -1);
        fill(vis2[i], vis2[i]+m, -1);
    }
    // 불이 난 곳과 지훈이가 갈 곳 모두 -1로 초기화한다.

    for(int i=0; i < n; i++)
    {
        cin >> board[i];
        // string이므로 하나만 받는다.
    }
    queue<pair<int,int>> q1;
    queue<pair<int,int>> q2;
    for(int i =0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(board[i][j] == 'F')
            {
                q1.push({i,j});
                vis1[i][j] = 0;
                // 불이 난 곳
            }
            if(board[i][j] == 'J')
            {
                q2.push({i,j});
                vis2[i][j] = 0;
                // 지훈이가 지나간 곳
            }
        }
    }
    while (!q1.empty())
    {
        auto cur = q1.front();
        q1.pop();

        for(int dir = 0; dir < 4; dir++)
        {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if(nx<0||nx>=n||ny<0||ny>=m) continue;
            if(vis1[nx][ny] >= 0||board[nx][ny] == '#') continue;

            vis1[nx][ny] = vis1[cur.X][cur.Y]+1;
            q1.push({nx,ny});
            // 불의 경우에는 평범하게 bfs를 돌리면 된다.
        }
    }
    while (!q2.empty())
    {
        auto cur = q2.front();
        q2.pop();

        for(int dir = 0; dir < 4; dir++)
        {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m)
            {
                cout << vis2[cur.X][cur.Y]+1;
                return 0;
                // 미로 외부로 빠져나간 경우는 탈출한 경우와 동일하다. 조건에 맞춰서 값을 출력한다.
            }
            if(vis2[nx][ny]>= 0 || board[nx][ny] == '#') continue;
            // 벽은 통과 불가능하다.
            if(vis1[nx][ny] != 1 && vis1[nx][ny] <= vis2[cur.X][cur.Y]+1) continue;
            // 불이 먼저 난 경우에는 지나갈 수 없다.
            vis2[nx][ny] = vis2[cur.X][cur.Y]+1;
            q2.push({nx,ny});
        }
    }
    cout << "IMPOSSIBLE";
    // 탈출하지 못하고 끝난경우 출력한다.
}