C++で解く：目的地までの道を切り開くために必要な最小パンチ回数を求めるプログラム

問題概要

H行W列のマトリックス（グリッド）が与えられます。各セルには「.」または「#」が格納されており、「.」は通行可能なスペース、「#」は通行できないブロックを表します。

Amalは家から市場へ向かいます。家はグリッドの左上隅のセルにあり、市場は右下隅にあります。Amalは上下左右の4方向に1セルずつ移動できますが、移動先は必ず通行可能なセルである必要があります。町の外に出ることや、ブロックされたセルに入ることはできません。

ただし、Amalの体力なら、自分で選んだ2×2セルの正方形領域内にあるすべてのブロックを、わずか1回のパンチで破壊し、そのセルを通行可能にすることができます。ここで、Amalが市場に到達するために必要な最小のパンチ回数を求めるのが本問題です。

入力例

この入力に対する出力は 1 になります。以下の図のように、赤で示した2×2領域を1回のパンチで破壊すれば、左上から右下へ抜ける経路が確保できるためです。

色付きのセル（元々ブロックだった箇所）を破壊することで、道が開けることが分かります。

解法のステップ

この問題は0-1 BFSという手法で効率的に解けます。通行可能なセルへの移動はコスト0、ブロックを破壊する必要がある移動はコスト1として扱い、両端キュー（deque）を活用することで最短コストを求めます。具体的な手順は以下の通りです。

n := マトリックスの行数
m := マトリックスの列数
(n + 1) × (m + 1) のサイズの2次元配列 dist を定義
両端キュー dq を定義
dq の先頭に (0, 0) を挿入
dist[0][0] := 0
dq が空でない間、以下を繰り返す：
    v := dq の先頭要素を取り出す
    i := 0 から i < 4 の間、i を 1 ずつ増やしながら繰り返す：
        x := dx[i] + v[0]
        y := dy[i] + v[1]
        もし x ≥ 0 かつ x < n かつ y ≥ 0 かつ y < m ならば：
            もし matrix[x][y] が '.' ならば：
                もし dist[x][y] > dist[v[0]][v[1]] ならば：
                    dist[x][y] := dist[v[0]][v[1]]
                    ペア { x, y } を dq の先頭に挿入
            そうでなければ（ブロックの場合）：
                p := x - 1 から p ≤ x + 1 の間、p を 1 ずつ増やしながら繰り返す：
                    q := y - 1 から q ≤ y + 1 の間、q を 1 ずつ増やしながら繰り返す：
                        もし p ≥ 0 かつ p < n かつ q ≥ 0 かつ q < m ならば：
                            もし dist[p][q] > dist[v[0]][v[1]] + 1 ならば：
                                dist[p][q] := dist[v[0]][v[1]] + 1
                                ペア { p, q } を dq の末尾に挿入
dist[n - 1][m - 1] を返す

ポイントは、コスト0の移動（通行可能セルへの移動）はキューの先頭に挿入し、コスト1の移動（パンチが必要な場合）はキューの末尾に挿入することです。これにより、距離の小さい状態から順に処理され、ダイクストラ法と同等の結果を高速に得られます。

C++による実装例

理解を深めるために、実際のC++コードを見てみましょう。

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

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

int solve(vector<vector<char>> matrix){
    int n = matrix.size();
    int m = matrix[0].size();
    vector<vector<int>> dist(n + 1, vector<int>(m + 1, 1e9));
    deque<array<int, 2>> dq;
    dq.push_front({ 0, 0 });
    dist[0][0] = 0;
    while (!dq.empty()){
        auto v = dq.front();
        dq.pop_front();
        for (int i = 0; i < 4; i++){
            int x = dx[i] + v[0], y = dy[i] + v[1];
            if (x >= 0 && x < n && y >= 0 && y < m){
                if (matrix[x][y] == '.'){
                    if (dist[x][y] > dist[v[0]][v[1]]){
                        dist[x][y] = dist[v[0]][v[1]];
                        dq.push_front({ x, y });
                    }
                } else{
                    for (int p = x - 1; p <= x + 1; p++){
                        for (int q = y - 1; q <= y + 1; q++){
                            if (p >= 0 && p < n && q >= 0 && q < m){
                                if (dist[p][q] > dist[v[0]][v[1]] + 1){
                                    dist[p][q] = dist[v[0]][v[1]] + 1;
                                    dq.push_back({ p, q });
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return dist[n - 1][m - 1];
}
int main(){
    vector<vector<char>> matrix = { { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' }, { '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, { '.', '.', '#', '.', '.' } };
    cout << solve(matrix) << endl;
}

入力

{ { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' },
{ '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, {
'.', '.', '#', '.', '.' } }

出力

1

まとめ

本記事では、2×2セルのブロックを1回のパンチで破壊できるという条件下で、グリッドの左上から右下へ移動する際の最小パンチ回数を求める問題を紹介しました。0-1 BFSを用いることで、計算量 O(H×W) で効率的に答えを求めることができます。両端キューへの挿入方向（先頭か末尾か）をコストに応じて使い分けるのが、この手法の重要なポイントです。