#bfs Algorithm 問題

問題リンク（韓国語）

4179번: 불!

翻訳

 

問題

Jを脱出させよう!

Jがいる迷路に火事が起こった。迷路でのJの位置と火の位置を考えて、

Jにひがつく前に脱出できるか。または、どのぐらいの時間がかかるかを計算しよう。

Jと火は1分ごとに1マス移動する。水平と垂直に移動する。(斜めにはできない)火は元の位置から四方に拡散する。Jは迷路のエッジで脱出できる。Jと火は壁を通れない。

 

入力

入力の最初の行には空白に区分された二つの整数RとCが与えられる。(1 ≤ R, C ≤ 1000 )

Rは迷路の行の数、Cは列の数である。

次の入力はR行の迷路が入力される。

# : 壁

.：通れる空間

J：Jの最初の位置

F：火事の最初の位置

 

出力

Jが火がつく前脱出できない場合は "IMPOSSIBLE”を出力する。

Jが迷路を脱出できる場合は一番速い脱出時間を出力する。

 

例題

入力	出力
4 4 #### #JF# #..# #..#	3

 

自分の答え

#define X first
#define Y second

//各位置に届ける時間
int J_time[1002][1002];
int F_time[1002][1002];
//各位置を訪ねたか
bool Jvis[1002][1002];
bool Fvis[1002][1002];

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

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    //行、列を入力
    int height, width;
    cin >> height >> width;
    
    string str[1002];
    queue<pair<int, int>> JQ; //Ｊ
    queue<pair<int, int>> FQ; //火

    for (int i = 0;i < height;i++) {
        cin >> str[i];
        fill(Jvis[i],Jvis[i]+width,0);
        fill(Fvis[i],Fvis[i]+width,0);
        fill(J_time[i], J_time[i] + width, -1);
        fill(F_time[i], F_time[i] + width, -1);
        for (int j = 0;j < width;j++) {
            if (str[i][j] == 'J') { //Jの位置入力
                JQ.push({ i,j });
                Jvis[i][j] = 1;
                J_time[i][j] = 0;
            }
            if (str[i][j] == 'F') { //火の位置入力
                FQ.push({ i,j });
                Fvis[i][j] = 1;
                F_time[i][j] = 0;
            }
        }
    }

    while (!FQ.empty()) {   //火が各位置に届ける時間の計算
        pair<int, int> cur = FQ.front();
        FQ.pop();
        for (int dir = 0;dir < 4;dir++) { //火が１マスづつ広がる
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || nx >= height || ny < 0 || ny >= width) continue;
            if (Fvis[nx][ny] || str[nx][ny] == '#') continue; //既に訪ねたことがある場合、壁の場合火が広がらない
            FQ.push({ nx,ny });
            Fvis[nx][ny] = 1;
            F_time[nx][ny] = F_time[cur.X][cur.Y]+1; 
        }

    }
    
    while (!JQ.empty()) { //Ｊの移動距離
        pair<int, int> curJ = JQ.front();
        JQ.pop();
        for (int dir = 0;dir < 4;dir++) { // Ｊの１マス
            int nx = curJ.X + dx[dir];
            int ny = curJ.Y + dy[dir];
            if (nx < 0 || nx >= height || ny < 0 || ny >= width) { //与えられた配列を脱したとき脱出成功！
                cout << J_time[curJ.X][curJ.Y] + 1;
                return 0;
            }
            if (Jvis[nx][ny] || str[nx][ny] == '#') continue;
            if(Fvis[nx][ny]&&J_time[curJ.X][curJ.Y] + 1 >= F_time[nx][ny]) continue; 　//ここがしんどかった
            JQ.push({ nx,ny });
            Jvis[nx][ny] = 1;
            J_time[nx][ny] = J_time[curJ.X][curJ.Y] + 1;

        }
    
    }
    cout << "IMPOSSIBLE";
}

if(Fvis[nx][ny]&&J_time[curJ.X][curJ.Y] + 1 >= F_time[nx][ny]) continue;

上の部分でミスして解決できなかった。

 

結論的には火とＪが壁で塞がっている場合を考えてなかったから

1番目の条件を考えなかった（Fvis[nx][ny])

Ｊと火が壁で分離されていれば、火が届かないところにも

Ｊはいけるべきだった。