C++で解く！マトリックス左上から右下への往復経路で獲得できる最大ポイントの求め方

はじめに

本記事では、マトリックス（グリッド）の左上から右下へ移動し、再び出発地点へ戻るまでの往復経路で獲得できるポイントの最大値を求めるプログラムを、C++の実装例とともに解説します。

グリッドの各セルは次の3種類の記号で表現されます。

• # … 通行できないブロックされた通路
• * … 獲得できるポイントが置かれたセル
• . … 通行可能な空きセル

目的は、左上の角から右下の角へ向かう移動（右・下方向のみ許可）と、そこから出発点へ戻る移動（左・上方向のみ許可）を組み合わせて、収集できるポイントを最大化することです。

解法の考え方

この問題の鍵は、「往復の経路」を「同時にスタートし、右・下方向のみで移動する2人のプレイヤー」の問題に読み替えることです。行きの経路を逆向きにたどれば帰りの経路と一致するため、この変換が成立します。ただし、2人が同じセルに到達した場合は、ポイントの二重カウントを避けて1度だけ加算しなければなりません。

さらに、2人は常に同じ対角線上（行番号＋列番号が等しい位置）に存在するため、一方の列の値はもう一方の行から導出できます。これにより状態数を大幅に削減でき、動的計画法（メモ化再帰）によって効率的に解くことが可能になります。

C++による実装例

#include <bits/stdc++.h>
#define MAX 5
#define N 5
#define M 5
#define inf 100000
using namespace std;
//ポイントを計算する関数
int cost(char grid[][M], int row1, int col1, int row2, int col2) {
   if (row1 == row2 && col1 == col2) {
      if (grid[row1][col1] == '*')
         return 1;
      return 0;
   }
   int ans = 0;
   if (grid[row1][col1] == '*')
      ans++;
   if (grid[row2][col2] == '*')
      ans++;
   return ans;
}
//最大ポイントを計算する関数
int solve(int n, int m, char grid[][M], int dp[MAX][MAX][MAX], int row1, int col1, int row2) {
   int col2 = (row1 + col1) - (row2);
   if (row1 == n - 1 && col1 == m - 1 && row2 == n - 1 && col2 == m - 1)
      return 0;
   if (row1 >= n || col1 >= m || row2 >= n || col2 >= m)
      return -1 * inf;
   if (dp[row1][col1][row2] != -1)
      return dp[row1][col1][row2];
   int ch1 = -1 * inf, ch2 = -1 * inf;
   int ch3 = -1 * inf, ch4 = -1 * inf;
   if (grid[row1][col1 + 1] != '#' &&
      grid[row2 + 1][col2] != '#')
   ch1 = cost(grid, row1, col1 + 1, row2 + 1, col2) + solve(n, m, grid, dp, row1, col1 + 1, row2 + 1);
   if (grid[row1][col1 + 1] != '#' &&
      grid[row2][col2 + 1] != '#')
   ch2 = cost(grid, row1, col1 + 1, row2, col2 + 1) + solve(n, m, grid, dp, row1, col1 + 1, row2);
   if (grid[row1 + 1][col1] != '#' &&
      grid[row2][col2 + 1] != '#')
   ch3 = cost(grid, row1 + 1, col1, row2, col2 + 1) + solve(n, m, grid, dp, row1 + 1, col1, row2);
   if (grid[row1 + 1][col1] != '#' &&
      grid[row2 + 1][col2] != '#')
   ch4 = cost(grid, row1 + 1, col1, row2 + 1, col2) + solve(n, m, grid, dp, row1 + 1, col1, row2 + 1);
   return dp[row1][col1][row2] = max({ch1, ch2, ch3, ch4});
}
int wrapper(int n, int m, char grid[N][M]) {
   int ans = 0;
   int dp[MAX][MAX][MAX];
   memset(dp, -1, sizeof dp);
   if (grid[n - 1][m - 1] == '#' || grid[0][0] == '#')
      ans = -1 * inf;
   if (grid[0][0] == '*')
      ans++;
   grid[0][0] = '.';
   if (grid[n - 1][m - 1] == '*')
      ans++;
   grid[n - 1][m - 1] = '.';
   ans += solve(n, m, grid, dp, 0, 0, 0);
   return max(ans, 0);
}
int main() {
   int n = 5, m = 5;
   char grid[N][M] = {
      { '.', '*', '.', '*', '.' },
      { '*', '#', '#', '#', '.' },
      { '*', '.', '*', '.', '*' },
      { '.', '#', '#', '#', '*' },
      { '.', '*', '.', '*', '.' }
   };
   cout << wrapper(n, m, grid) << endl;
   return 0;
}

コードのポイント

• cost() 関数は、2人の現在位置に対応するポイントを計算します。同一セルの場合は二重カウントを避けて1度だけ加算します。
• solve() 関数はメモ化再帰により、2人の移動パターン（右＋下、右＋右、下＋右、下＋下）の4通りの選択肢を試し、その中で最大値を返します。
• wrapper() 関数は、スタートとゴールのセルがブロックされていないかの判定や、両端のセルのポイント加算など、全体の初期処理を担います。

出力

8