C++で障害物を除去しながらグリッド内の最短経路を求める方法

問題概要

m × n のグリッドが与えられます。各セルは 0 または 1 のいずれかの値を持ち、0 は空きセル、1 は障害物(ブロックされたセル)を表します。1 ステップごとに、現在いる空きセルから上下左右のいずれかの方向へ移動できます。「最大 k 個までの障害物を除去できる」という条件下で、左上隅のセル (0, 0) から右下隅のセル (m-1, n-1) まで移動するために必要な最小ステップ数を求めてください。到達可能な経路が存在しない場合は -1 を返します。

入力例

このグリッドに対して k = 1 を与えたとき、出力は 6 になります。障害物をまったく除去しない場合の最短経路は 10 ステップかかりますが、位置 (3, 2) の障害物を 1 つ除去すると 6 ステップに短縮できます。実際の経路は (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (3,2) → (4,2) となります。

解法のアプローチ

この問題は、幅優先探索(BFS)とメモ化(DP)を組み合わせることで効率よく解けます。dp[x][y][k] を「位置 (x, y) に、残り除去回数 k の状態で到達するまでの最小ステップ数」と定義することで、同一状態の再探索を防ぎつつ、障害物の除去状況ごとの最短距離を正確に管理できます。

具体的には、以下の手順で進めます。

• ok() 関数を定義し、座標 (x, y) が r 行 c 列のグリッドの範囲内にあるかどうかを判定できるようにします。
• サイズ 50 × 50 × 2000 の三次元配列 dp を定義します。
• x、y、k、length の 4 つのフィールドを持つデータ構造 Data を定義します。

メイン処理の流れ

1. dp をすべて無限大(INT_MAX)で初期化します。
2. r := 行数、c := 列数 とします。
3. キュー q を用意します。
4. Data オブジェクト root(x = 0、y = 0、k、length = 0)を作成し、q に挿入します。
5. q が空になるまで次を繰り返します。
   • キューの先頭要素を取り出し、node とします。
   • x := node.x、y := node.y、k := node.k、length := node.length とします。
   • x が r - 1 かつ y が c - 1 と一致すれば、length を返します。
   • length を 1 増やします。
   • i を 0 ~ 3 まで変化させながら、4 方向それぞれについて以下を処理します。
     • nx := x + dir[i][0]、ny := y + dir[i][1] とします。
     • (nx, ny) がすでに右下隅 (r-1, c-1) であれば、length を返します。
     • ok(nx, ny, r, c) が真である場合:
       • grid[nx][ny] が 0(空きセル)のとき:length < dp[nx][ny][k] であれば、新しい Data(nx, ny, k, length) を q に追加し、dp[nx][ny][k] := length と更新します。
       • それ以外(障害物がある)のとき:k > 0 かつ length < dp[nx][ny][k] であれば、障害物を 1 つ消費したものとして新しい Data(nx, ny, k - 1, length) を q に追加し、dp[nx][ny][k] := length と更新します。
6. キューが空になっても目的地へ到達できなければ、-1 を返します。

BFS を採用するのは、移動コストがすべて均一(1 ステップ)だからです。BFS は始点から近い順にノードを展開するため、目的地へ最初に到達した時点のステップ数が必ず最短になります。そこへ dp による枝刈りを組み合わせることで、無駄な探索を大幅に削減できます。

計算量の目安

状態数は「マスの位置 (m × n) × 残り除去回数 (k + 1)」となるため、時間計算量・空間計算量はともに O(m × n × k) です。典型的な制約(m, n ≤ 40、k ≤ m × n)では、50 × 50 × 2000 の dp 配列で十分対応でき、高速に動作します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
int dir [4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int dp[50][50][2000];
struct Data{
    int x, y, k, length;
    Data(int a, int b, int c, int d){
        x = a;
        y = b;
        k = c;
        length = d;
    }
};
class Solution {
    public:
    void pre(){
        for (int i = 0; i < 50; i++) {
            for (int j = 0; j < 50; j++) {
                for (int k = 0; k < 2000; k++) {
                    dp[i][j][k] = INT_MAX;
                }
            }
        }
    }
    bool ok(int x, int y, int r, int c){
        return (x < r && y < c && x >= 0 && y >= 0);
    }
    int shortestPath(vector<vector<int> >& grid, int k){
        pre();
        int r = grid.size();
        int c = grid[0].size();
        queue<Data> q;
        Data root(0, 0, k, 0);
        q.push(root);
        while (!q.empty()) {
            Data node = q.front();
            q.pop();
            int x = node.x;
            int y = node.y;
            int k = node.k;
            int length = node.length;
            if (x == r - 1 && y == c - 1)
            return length;
            length++;
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                if (nx == r - 1 && ny == c - 1)
                return length;
                if (ok(nx, ny, r, c)) {
                    if (grid[nx][ny] == 0) {
                        if (length < dp[nx][ny][k]) {
                            q.push(Data(nx, ny, k, length));
                            dp[nx][ny][k] = length;
                        }
                    }
                    else {
                        if (k > 0 && length < dp[nx][ny][k]) {
                            q.push(Data(nx, ny, k - 1, length));
                            dp[nx][ny][k] = length;
                        }
                    }
                }
            }
        }
        return -1;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{0,0,0},{1,1,0},{0,0,0},{0,1,1},
    {0,0,0}};
    cout << (ob.shortestPath(v, 1));
}

入力

{{0,0,0},{1,1,0},{0,0,0},{0,1,1},{0,0,0}}

出力

6