問題概要

$H \times W$ のグリッドがあって、各マスは通路マス (.) か壁マス (#) のいずれかです。

今、左上のマス $(1, 1)$ から右下のマス $(H, W)$ へと移動したいです。上下左右に移動することができます。通路マスは自由に通ることができますが、壁マスには入れません。

ただし、1 回パンチをすることで、任意の場所の $2 \times 2$ のマスを選んで、その区画内にある壁をすべて破壊することができます。

スタートからゴールまで行けるようにするためには、最低何回パンチを繰り出せばよいか求めてください。

制約

$2 \le H, W \le 500$

パンチを言い換える

「器物損壊！高橋君」では、「1 回のパンチで 1 個の壁を壊せる」という設定でした。その場合は次のようなグラフを考えればよかったです。各マスを頂点としたグラフ (有向) において

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

としたグラフの最短路長を求めればよいということになりました。今回の問題では「1 回のパンチで $2 \times 2$ の範囲の壁を壊せる」という設定になります。その場合は次のように考えましょう。おそらくこの言い換えが難しいと思われます。

任意のマスから通路マスへ、重み 0 の辺を張る
任意のマス (下図の T マス) から、下図の A マスへ、重み 1 の辺を張っておく
- T マスから 1 回のパンチで行けるマスを A で示しています
- 上下左右へのマスのみに辺を張るわけではないことに注意

.......
..AAA..
.AAAAA.
.AATAA.
.AAAAA.
..AAA..
.......

つまり、今いるマスから 1 回の魔法で行ける範囲が広がったことになります。

一つ注意したいのは、T マスから A マスへの移動のうち、実際には壁がないマスへの移動も含まれる可能性があることです。そのような移動には無駄にコスト 1 をかけることになります。しかし、通路間の移動にはコスト 0 の辺が他で張られていますので、実際に最短路を求めるときにはそっちが使われることになります。よって気にしなくてよいです。

0-1 BFS へ

こうして、辺の重みが 0 または 1 であるようなグラフができましたので、0-1 BFS を用いて解くことができます。このようなグラフにおいても、各頂点から伸びる辺の本数は高々定数ですので、辺数は $O(VE)$ と評価できます。よって計算量は $O(HW)$ となります。

0-1 BFS については、次の記事にて。

drken1215.hatenablog.com

コード

#include <bits/stdc++.h>
using namespace std;

// 四方向への移動
const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};

// 無限大
const int INF = 1<<29;

// マスを表す構造体
using pint = pair<int,int>;

int main() {
    // 入力
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];

    // deque
    deque<pint> que;
    vector<vector<int>> dp(H, vector<int>(W, INF));
    que.push_back({0, 0});
    dp[0][0] = 0;

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

        // 通路マスへの移動
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (fi[nx][ny] == '#') continue;

            // 移動コストは 0 なので que の front に push
            if (dp[nx][ny] > dp[x][y]) {
                dp[nx][ny] = dp[x][y];
                que.push_front({nx, ny});
            }
        }

        // 魔法を唱えて移動
        for (int nx = x - 2; nx <= x + 2; ++nx) {
            for (int ny = y - 2; ny <= y + 2; ++ny) {
                if (abs(nx - x) + abs(ny - y) == 4) continue;
                if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;

                // 壁だろうが通路だろうがコスト 1 の辺を張る
                // コスト 1 なので que の back に push
                if (dp[nx][ny] > dp[x][y] + 1) {
                    dp[nx][ny] = dp[x][y] + 1;
                    que.push_back({nx, ny});
                }
            }
        }
    }
    cout << dp[H-1][W-1] << endl;
}