【C++】上下左右への移動が可能なグリッドにおける最小コストパスの求め方

問題概要

2次元配列（グリッド）があり、各セルにはそのセルを通過するために必要なコストを表す数値が格納されています。左上のセルから右下のセルへ移動するとき、合計コストが最小となる経路を見つけるのが目的です。この問題のポイントは、上下左右の4方向への移動がすべて許可されているという点です。

例えば、次のような入力が与えられたとします。

この場合の出力は 340 となります。これは (32 + 11 + 14 + 48 + 66 + 13 + 19 + 7 + 34 + 12 + 21 + 42 + 21) = 340 に対応します。

解法のアプローチ

移動が「右」と「下」だけに制限されていれば、単純な動的計画法（DP）で解けます。しかし今回は上下左右すべての方向への移動が許可されているため、ダイクストラ法を応用します。std::set を優先度付きキューとして利用し、常に現時点で最小コストのセルから探索を広げることで、各セルへの最小コストを順に確定させていきます。

具体的な手順は以下の通りです。

• x座標・y座標・距離（コスト）を持つ cell クラスを定義します。
• row × col のサイズの matrix 配列を定義し、全要素を無限大（INT_MAX）で初期化します。
• 4方向の移動を表す配列 dx = {-1, 0, 1, 0} と dy = {0, 1, 0, -1} を用意します。
• cell 型のセット st を定義し、cell(0, 0, 0) を挿入します。
• matrix[0][0] = grid[0][0] と設定します。
• st が空になるまで、以下を繰り返します。
  • st の先頭要素（最小コストのセル）を取り出して削除します。
  • 4方向それぞれについて、隣接セルの座標 (x, y) を計算します。
  • (x, y) がグリッドの範囲外であれば、次の反復へスキップします。
  • matrix[x][y] > matrix[k.x][k.y] + grid[x][y] が成り立つ場合：
    • matrix[x][y] が INT_MAX でなければ、st から古いエントリ cell(x, y, matrix[x][y]) を検索して削除します。
    • matrix[x][y] を新しい最小コストで更新し、st に挿入し直します。
• 最後に matrix[row - 1][col - 1] を返します。

実装例

理解を深めるために、以下のC++実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
#define ROW 5
#define COL 5
class cell {
    public:
    int x, y;
    int distance;
    cell(int x, int y, int distance) :
    x(x), y(y), distance(distance) {}
};
bool operator<(const cell& a, const cell& b) {
    if (a.distance == b.distance) {
        if (a.x != b.x)
            return (a.x < b.x);
        else
            return (a.y < b.y);
    }
    return (a.distance < b.distance);
}
bool isOk(int i, int j) {
    return (i >= 0 && i < COL && j >= 0 && j < ROW);
}
int solve(int grid[ROW][COL], int row, int col) {
    int matrix[row][col];
    for (int i = 0; i < row; i++)
    for (int j = 0; j < col; j++)
    matrix[i][j] = INT_MAX;
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    set<cell> st;
    st.insert(cell(0, 0, 0));
    matrix[0][0] = grid[0][0];
    while (!st.empty()) {
        cell k = *st.begin();
        st.erase(st.begin());
        for (int i = 0; i < 4; i++) {
            int x = k.x + dx[i];
            int y = k.y + dy[i];
            if (!isOk(x, y))
                continue;
            if (matrix[x][y] > matrix[k.x][k.y] + grid[x][y]){
                if (matrix[x][y] != INT_MAX)
                    st.erase(st.find(cell(x, y, matrix[x][y])));
                matrix[x][y] = matrix[k.x][k.y] + grid[x][y];
                st.insert(cell(x, y, matrix[x][y]));
            }
        }
    }
    return matrix[row - 1][col - 1];
}
int main() {
    int grid[ROW][COL] = {
        32, 101, 66, 13, 19,
        11, 14, 48, 158, 7,
        101, 114, 175, 12, 34,
        89, 126, 42, 21, 141,
        100, 33, 112, 42, 21
    };
    cout << solve(grid, ROW, COL);
}

入力

{32, 101, 66, 13, 19,
11, 14, 48, 158, 7,
101, 114, 175, 12, 34,
89, 126, 42, 21, 141,
100, 33, 112, 42, 21
};

出力

340

まとめ

このアルゴリズムの計算量は O(row × col × log(row × col)) です。これは std::set への挿入・削除・検索が対数時間で行われるためです。上下左右への移動が許可されるグリッド上の最短経路問題では、単純なDPでは更新順序の循環が発生しうるため、ダイクストラ法のように「現時点で最小コストのセルから確定させていく」手法が有効です。優先度付きキューとして priority_queue を使っても同様に実装できます。