C++で解説：グリッドの一方の端から反対側の端へ到達するために必要な最小変更回数を求める方法

問題概要

ここでは、x × y のサイズを持つグリッドが与えられるとします。グリッドには「ブロックされたセル」と「通行可能なセル」の2種類が存在し、ブロックされたセルには進入できません。グリッドは2次元配列として表現され、ブロックされたセルは #、通行可能なセルは . で表されます。

目標は、左上のセル (0, 0) から右下のセル (x-1, y-1) へ移動することです。ただし、移動は「右へ進む」か「下へ進む」の2種類のみが許されており、通れるのは通行可能なセルだけです。なお、始点と終点はどちらも通行可能であることが保証されています。

仮に現状のままでは目的地へ到達できない場合でも、ブロックされたセルを通行可能なセルへ変更する操作を行うことで道を開けます。求めたいのは、始点から目的地まで到達するために必要な最小の変更操作回数です。

入力例と出力例

例として、x = 4、y = 4、grid = {"..#.", "#.#.", "#.##", "###."} が与えられた場合を考えてみましょう。このときの出力は 1 になります。

これは、経路上のブロックされたセルをわずか1つ（例えば (2, 3)）通行可能へ変更するだけで、(0, 0) から (3, 3) へ至る経路が確保できるためです。

解法のアプローチ（動的計画法）

この問題は動的計画法（DP）を使うと効率よく解けます。mat[i][j] を「セル (i, j) に到達するまでに必要な最小の変更回数」と定義します。隣接するセルへ移動するとき、通行可能なセルからブロックされたセルへ移り変わる瞬間にコスト 1 が加算されると考えます。あとは各マスについて「下方向」「右方向」への遷移を順番に処理し、最小値を更新していくだけです。

手順

2次元配列 mat を用意する
if grid[0][0] == '#' ならば:
   mat[0][0] := 1
それ以外の場合:
   mat[0][0] := 0
for i := 0 to x-1:
   for j := 0 to y-1:
      if i + 1 < x ならば:
         mat[i + 1][j] = min(mat[i + 1][j], mat[i][j] + (grid[i + 1][j] == '#' かつ grid[i][j] == '.' のとき 1))
      if j + 1 < y ならば:
         mat[i][j + 1] = min(mat[i][j + 1], mat[i][j] + (grid[i][j + 1] == '#' かつ grid[i][j] == '.' のとき 1))
return mat[x - 1][y - 1]

C++による実装例

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

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

int solve(int x, int y, vector<string> grid){
    vector<vector<int>> mat(x, vector<int>(y, 100));
    if(grid[0][0] == '#')
        mat[0][0] = 1;
    else
        mat[0][0] = 0;
    for(int i = 0; i < x; i++){
        for(int j = 0; j < y; j++){
            if(i + 1 < x){
                mat[i + 1][j] = min(mat[i + 1][j], mat[i][j] + (grid[i + 1][j] == '#' && grid[i][j] == '.'));
            }
            if(j + 1 < y){
                mat[i][j + 1] = min(mat[i][j + 1], mat[i][j] + (grid[i][j + 1] == '#' && grid[i][j] == '.'));
            }
        }
    }
    return mat[x - 1][y - 1];
}
int main() {
    int x = 4, y = 4;
    vector<string> grid = {"..#.", "#.#.", "#.##", "###."};
    cout<< solve(x, y, grid);
    return 0;
}

入力

4, 4, {"..#.", "#.#.", "#.##", "###."}

出力

1

このアルゴリズムは、グリッドの各マスを一度ずつ処理するだけでよいため、計算量は O(x × y) となり、非常に効率的です。同様のDPの考え方は、迷路やパス検索の問題全般に応用できるので、ぜひ覚えておきましょう。