問題概要

$H \times W$ のマス目で表現された地図が与えられます。

. は通路、# は壁を表します。s マスから出発して、上下左右への移動を繰り返しながら g マスへと到達したいとします。. マスには進めますが、# マスには進めません。

s から g へと到達できない場合、何個かの # マスを破壊することで到達可能になるようにしたいとします。高々 2 個以内の # マスを破壊することで到達できるかどうかを判定してください。

制約

$1 \le H, W \le 500$

考えたこと

各マスを頂点としたグラフ (有向にします) において

通路マスから通路マスへの辺の重みは 0
通路マスから壁マスへの辺の重みは 1
壁マスから通路マスへの辺の重みは 0
壁マスから壁マスへの辺の重みは 1

としたグラフの最短路長を求めればよいということになります。最短路長が 2 以下であれば "YES"、2 より大きければ "NO" と判定することができます。

重みが非負であるような重み付きグラフですので、Dijkstra 法で解くことができます。その場合計算量は $O(HW(\log H + \log W))$ となります。今回の問題では、これでも十分 AC をとることができます。

0-1 BFS

しかし重み付きグラフの辺の重みが 0 と 1 のみに限られる場合、Dijkstra 法における priority_queue を工夫することで、さらに計算量を落とせることが知られています (通称 0-1 BFS)。

辺の重みが 0 と 1 のみに限られるとき、Dijkstra 法を回したときの priority_queue の中身は常に「最大値と最小値との差が 1 以下」という状態が保たれるのです。

もし最大値と最小値との差が 2 以上であった場合は、Dijkstra 法のある段階において、ある辺 $e = (u, v)$ の緩和をしたときに、dist[v] の値が `dist[u]' + 2 以上になっていたことを意味します。これは辺の重みが 0, 1 のみであることに矛盾します。

よって、priority_queue の中身は高々 2 種類の値しか同時に共存しないことになります。priority_queue のような高級なデータ構造を使う必要はありません。代わりに

両端キュー deque を使う

という方法が考えられます。そして辺 $e = (u, v)$ について緩和するとき、

辺のコストが 0 の場合：deque の先頭に push
辺のコストが 1 の場合：deque の末尾に push

というようにすればよいことになります。このように改良した解法の計算量は $O(HW)$ となります。

0-1 BFS の類題

0-1 BFS を使って解ける問題たち

drken1215.hatenablog.com

コード

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

// 無限大を表す値
const int INF = 1<<29;

// 上下左右への動きを表すベクトル
const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};

int main() {
    // 入力
    int H, W;  // 縦の長さ, 横の長さ
    cin >> H >> W;
    vector<string> field(H);
    for (int i = 0; i < H; ++i) cin >> field[i];

    // スタートとゴールのマスを割り出す
    int sx = -1, sy = -1, gx = -1, gy = -1;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (field[i][j] == 's') sx = i, sy = j;
            if (field[i][j] == 'g') gx = i, gy = j;
        }
    }

    // 各頂点は pair<int,int> 型で表すことにする
    using Node = pair<int,int>;
    deque<Node> que;  // deque 

    // 初期条件
    // dist[i][j] はマス (i, j) への最短路長を表す
    que.push_front(Node(sx, sy));
    vector<vector<int>> dist(H, vector<int>(W, INF));
    dist[sx][sy] = 0;

    // 0-1 BFS 開始
    while (!que.empty()) {
        // deque の先頭の要素を取り出す
        auto [x, y] = que.front();
        que.pop_front();

        // 隣接頂点を順にみていく
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            // 盤面外はスキップ
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;

            // コスト 0 の場合は、deque の先頭に push
            if (field[nx][ny] != '#') {
                if (dist[nx][ny] > dist[x][y]) {
                    dist[nx][ny] = dist[x][y];
                    que.push_front(Node(nx, ny));
                }
            }
            // コスト 1 の場合は、deque の末尾に push
            else {
                if (dist[nx][ny] > dist[x][y] + 1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    que.push_back(Node(nx, ny));
                }
            }
        }
    }

    // 最短路長
    if (dist[gx][gy] <= 2) cout << "YES" << endl;
    else cout << "NO" << endl;
}