C++プログラムで解く！行列内の往復パスにおける最大合計の求め方

この問題では、サイズ n×m の行列 mat[][] が与えられます。求めるのは、行列を上から下へ進み、その後再び上へ戻る一連の経路の中で、通過したセルの合計値が最大になるパスです。本記事では、その解法をC++プログラムとともにわかりやすく解説します。

問題の説明

左上のセル mat[0][0] から右下のセル mat[n−1][m−1] までの経路と、そこから再び mat[0][0] へ戻る経路の2つを見つけ、それぞれの合計値の和を最大化することが目的です。

有効な移動

mat[0][0] から mat[n−1][m−1] へ：
　・右へ移動（mat[i][j] → mat[i][j+1]）
　・下へ移動（mat[i][j] → mat[i+1][j]）

mat[n−1][m−1] から mat[0][0] へ：
　・左へ移動（mat[i][j] → mat[i][j−1]）
　・上へ移動（mat[i][j] → mat[i−1][j]）

重要な制約として、行きと帰りの両方のパスが完全に一致してはいけません。2つのパスには、少なくとも1つ以上の異なるセルが含まれている必要があります。

入出力例で問題を理解する

入力

mat[][] = {
    {1, 2, 4},
    {3, 0, 1},
    {5, −1, −1}
}

出力

15

説明

mat[0][0] から mat[n−1][m−1] へのパス：1 + 3 + 5 − 1 − 1 = 7
mat[n−1][m−1] から mat[0][0] へのパス：1 + 4 + 2 + 1 = 8
合計 = 7 + 8 = 15

解法アプローチ

この問題を素直に考えると、「mat[0][0] から mat[n−1][m−1] へのパス」と「mat[n−1][m−1] から mat[0][0] へのパス」の2つを別々に扱うことになります。しかし、より効率的な方法は、両方のパスを「mat[0][0] から mat[n−1][m−1] へ向かう2つの異なるパス」として同時に処理することです。帰りのパスは、行きのパスを逆向きにたどったものとみなせるためです。

具体的には、開始地点 mat[0][0] から2つのパスを同時に進めていき、各ステップで最も有望な次のセルを選択しながら終点まで到達させます。このとき、同じセルが両方のパスに含まれないよう注意が必要です。仮に両パスが同一セル上にある場合は、そのセルの値は一度だけ加算します。

さらに、計算量を抑えるために動的計画法（メモ化）を活用します。2つのパスを同時に進める場合、「行のインデックス＋列のインデックス」の値が常に等しいという性質があるため、一方のパスの位置が決まれば、もう一方のパスの列の位置も自動的に導出できます。これにより、DPテーブルの状態数を削減し、効率的に最大合計を求められます。

サンプルプログラム

以下は、この解法の動作を示すC++プログラムです。

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

// 2つのパス上のセルの合計を計算（同一セルの場合は1回のみ）
int CalcNodeDiff(int mat[][row], int path1x, int path1y, int path2x, int path2y) {
    if (path1x == path2x && path1y == path2y) {
        return mat[path1x][path1y];
    }
    return mat[path1x][path1y] + mat[path2x][path2y];
}

// 最大合計パスを動的計画法で求める関数
int calcMaxPathSumOfMat(int mat[][row], int path1x, int path1y, int path2x, int n) {
    int pathSumDP[5][5][5];
    memset(pathSumDP, −1, sizeof(pathSumDP));
    int path2y = path1x + path1y − path2x;
    int maxPathSum = −10000;
    if (path1x >= n || path2x >= n || path1y >= row || path2y >= row)
        return 0;
    if (pathSumDP[path1x][path1y][path2x] != −1)
        return pathSumDP[path1x][path1y][path2x];
    maxPathSum = max(maxPathSum,
        calcMaxPathSumOfMat(mat, path1x + 1, path1y, path2x + 1, n) +
        CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
    maxPathSum = max(maxPathSum,
        calcMaxPathSumOfMat(mat, path1x, path1y + 1, path2x, n) +
        CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
    maxPathSum = max(maxPathSum,
        calcMaxPathSumOfMat(mat, path1x, path1y + 1, path2x + 1, n) +
        CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
    maxPathSum = max(maxPathSum,
        calcMaxPathSumOfMat(mat, path1x + 1, path1y, path2x, n) +
        CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
    pathSumDP[path1x][path1y][path2x] = maxPathSum;
    return maxPathSum;
}

int main() {
    int n = 3;
    int mat[n][row] = {
        { 1, 2, 4 },
        { 3, 0, 1 },
        { 5, −1, −1 }
    };
    cout<<"The maximum sum path in a matrix from top to bottom and back is "<<calcMaxPathSumOfMat(mat, 0, 0, 0, n);
    return 0;
}

出力

The maximum sum path in a matrix from top to bottom and back is 15