【競プロ】01-BFS を使ってみる

前回BFSをテーマに記事を書きましたが、その続き的なものです。BFSを知らない人は先に以下の記事を読んでみてください。

【競プロ】BFSを理解しよう

2020年4月12日

今回はその続きとして01-BFSと呼ばれるものを取り上げます。実装は普通のBFSとほぼ変わりませんが、面白いアルゴリズムです。
今回も問題を解きながら説明します。

ARC5 C問題器物損壊！高橋君

前回と同じように解くのは難しそうです。少し考え方を変えて「gに行くまでに、最低で何回塀を壊す必要があるのか」を求めましょう。これが2以下であればYESを出力すればいいです。

これを求めるために01-BFSを使います。上から \(x\)、下から \(y\) のマスを座標 \((x,y)\) で表すとし、「\((x,y)\) に行くまでに、最低で何回塀を壊す必要があるのか」について考えましょう。

こうすると前回の最短経路の問題と似ているような感じがします。あるマスから塀のマスへ進むとき、壊す塀の数が1増えます。ただの道に進む時、壊す塀の数は変化しません。

この移動時の変化を図に整理します。次のような迷路が与えられた時（入力例1）、

次の図のようなイメージで考えられます。

壊す塀の最小値を効率よく求めましょう。

最短経路を考えるときは、スタートに近いマスからキューに放り込んで調べていくことで求められました。塀は極力壊したくないので、上の図で言う「０」の矢印に進むことを優先するべきです。

逆に「１」の矢印はどうしてもという場合だけ選び、探索は後回しにしたいです。

これは両端キュー（deque）を用いて実装できます。キューは最初に入れたものから順に取り出しますが、両端キューは先頭に割り込ませることができます。

データは全て先頭から取り出すとして、「0」の矢印の先のマスは両端キューの先頭へ、「1」の矢印の先のマスは後尾へ追加することで、「後回し」できます。

dequeの主な機能もまとめておきます。

duque<int> dqとすることでint型を扱うdequeが宣言できます。
例えば、dq.push_back(1)とすることで語尾に1が追加されます。
例えば、dq.push_front(1)とすることで先頭に1が追加されます。
dq.front()とすることで先頭要素が得られます。
dq.back()とすることで後尾要素が得られます。
dq.pop_front()とすることで先頭要素を取り除けます。
dq.pop_back()とすることで後尾要素を取り除けます。
dq.empty()とすることでdqが空であるかの真偽値が得られます。

前回と変わるのはキューへ要素を追加するところだけです。コード内での座標は \(\ [y][x]\) で指定していることに注意してください。

また前回の記事でも説明しましたが、配列 \(dy,dx\) は以下の図の4つのベクトルの組を表し、これを使って座標の移動を簡潔に表せます。

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

int main(){
    int h,w;
    cin >> h >> w;
    vector<vector<char>> maze(h,vector<char>(w));
    pair<int,int> s,g;
    rep(i,h) rep(j,w){
        cin >> maze[i][j];
        if(maze[i][j] == 's') s = make_pair(i,j);
        if(maze[i][j] == 'g') g = make_pair(i,j);
    }

    deque<pair<int,int>> dq;
    dq.push_back(s);
    // ある座標までに破壊する塀の数
    vector<vector<ll>> des(h,vector<ll>(w,INF));
    des[s.first][s.second] = 0;
    vector<int> dy = {0,1,0,-1};
    vector<int> dx = {1,0,-1,0};
    while(!dq.empty()){
        int y = dq.front().first;
        int x = dq.front().second;
        dq.pop_front();

        if(y == g.first && x == g.second) break;
        rep(i,4){
            int ny = y+dy[i];
            int nx = x+dx[i];
            if(ny < 0 || ny > h-1 || nx < 0 || nx > w-1)
                continue;

            if(des[ny][nx] == INF){
                if(maze[ny][nx] == '#'){
                    des[ny][nx] = des[y][x]+1;
                    dq.push_back(make_pair(ny,nx));
                }else{
                    des[ny][nx] = des[y][x];
                    dq.push_front(make_pair(ny,nx));
                }
            }
        }
    }

    if(des[g.first][g.second] <= 2) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}