C++で最大スコアとなる経路の数を求める方法

問題の概要

文字が書かれた正方形のマス目(ボード)を考えます。スタート地点は右下の「S」とマークされたマスで、ゴールは左上の「E」とマークされたマスです。それ以外のマスには、1〜9の数字か、障害物を表す「X」が書かれています。1回の移動では、移動先に障害物がない場合に限り、「上」「左」「左上」のいずれかに進むことができます。

求めるのは、次の2つの要素からなるリストです。

• 通過したマスの数字を集めたときに得られる最大の合計値
• その最大合計を実現する経路の本数

答えは 10^9 + 7 で割った余りとして返します。経路が1つも存在しない場合は [0, 0] を返します。

例として、board = ["E12", "1X1", "21S"] が入力された場合、出力は [1, 2] となります。

解法のアプローチ(動的計画法)

この問題は動的計画法(DP)で効率よく解けます。dp[i][j][0] にはマス (i, j) からゴールまでの最大スコアを、dp[i][j][1] にはそのスコアを達成する経路数を格納します。具体的な手順は以下の通りです。

1. n を行数、m を列数とします。
2. n × m × 2 のサイズを持つ3次元配列 dp を定義します。
3. ゴール地点を dp[n-1][m-1][0] = 0、dp[n-1][m-1][1] = 1 で初期化します。
4. 最下行について、i を m-2 から 0 まで減らしながら処理します。
   • b[n-1][i] が 'X' の場合はループを中断します。
   • dp[n-1][i][0] = b[n-1][i] - '0' + dp[n-1][i+1][0]
   • dp[n-1][i][1] += dp[n-1][i+1][1]
5. 最終列についても、i を n-2 から 0 まで減らしながら同様に処理します。
6. 残りのすべてのマスについて、i を n-2 から 0 へ、j を m-2 から 0 へ減らしながら処理します。
   • b[i][j] が 'X' の場合はスキップします。
   • dp[i][j][0] を設定します('E' なら 0、それ以外なら b[i][j] - '0')。
   • maxVal を dp[i][j+1][0]、dp[i+1][j][0]、dp[i+1][j+1][0] の最大値とします。
   • maxVal が 0 で、かつ隣接する3つのマスのどこにも 'S' がない場合は、そのマスへ到達できないため dp[i][j][0] = 0 として次の反復へ進みます。
   • dp[i][j][0] += maxVal とします。
   • 隣接マスの dp スコアが maxVal と一致している場合、それぞれの経路数 dp[*][*][1] を加算します。
   • 最後に dp[i][j][1] と dp[i][j][0] を m(= 10^9 + 7)で割った余りに更新します。
7. 最後に dp[0][0](最大スコアと経路数のペア)を返します。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    } cout << "]"<<endl;
}
typedef long long int lli;
const lli m = 1e9 + 7;
lli add(lli a, lli b){
    return ((a % m) + (b % m) % m);
} class Solution {
    public:
    vector<int> pathsWithMaxScore(vector<string>& b) {
       int n = b.size();
       int m = b[0].size();
       vector < vector < vector <int> > > dp(n, vector < vector
       <int> >(m, vector <int> (2)));
       dp[n - 1][m - 1][0] = 0;
       dp[n - 1][m - 1][1] = 1;
       for(int i = m - 2; i >= 0; i--){
          if(b[n - 1][i] == 'X')break;
          dp[n - 1][i][0] = b[n - 1][i] - '0' + dp[n - 1][i + 1]
          [0];
          dp[n - 1][i][1] += dp[n - 1][i + 1][1];
       }
       for(int i = n - 2; i >= 0; i--){
          if(b[i][m - 1] == 'X')break;
          dp[i][m - 1][0] = b[i][m - 1] - '0' + dp[i + 1][m - 1]
          [0];
          dp[i][m - 1][1] += dp[i + 1][m - 1][1];
       }
       for(int i = n - 2; i >= 0; i--){
          for(int j = m - 2; j >= 0; j--){
             if(b[i][j] == 'X')continue;
             dp[i][j][0] = b[i][j] == 'E' ? 0 :b[i][j] - '0';
             int maxVal = max({dp[i][j + 1][0], dp[i + 1][j][0],
             dp[i + 1][j + 1][0]});
             if(maxVal == 0 && (b[i+1][j] != 'S' && b[i][j + 1] !
             = 'S' && b[i+1][j + 1] != 'S')){
                dp[i][j][0] = 0;
                continue;
             }
             dp[i][j][0] += maxVal;
             if(dp[i + 1][j][0] == maxVal){
                dp[i][j][1] += dp[i + 1][j][1];
             }
             if(dp[i + 1][j + 1][0] == maxVal){
                dp[i][j][1] += dp[i + 1][j + 1][1];
             }
             if(dp[i][j + 1][0] == maxVal){
                dp[i][j][1] += dp[i][j + 1][1];
             }
             dp[i][j][1] %= m;
             dp[i][j][0] %= m;
          }
       }
       return dp[0][0];
    }
};
main(){
    Solution ob;
    vector<string> v = {"E12","1X1","21S"};
    print_vector(ob.pathsWithMaxScore(v));
}

入力

{"E12","1X1","21S"}

出力

[1, 2]