C ++中得分最高的路径数

假设我们有一个方形的字符板。我们可以从右下角标有“ S”的方框开始在板上移动。现在我们需要到达标记有字符“ E”的左上角正方形。其他正方形用从1到9的数字字符或障碍物“ X”标记。一举一动，只有在没有障碍物的情况下，我们才能向上，向左或向左上走。

我们必须找到两个数字的列表：第一个数字是我们可以收集的数字字符的最大和，第二个数字是我们可以用来获得最大和的此类路径的数量。对于答案，以10 ^ 9 + 7为模。如果没有路径，则返回[0，0]。

因此，如果输入类似于board = [“ E12”，“ 1X1”，“ 21S”]，则输出将为[1,2]

为了解决这个问题，我们将遵循以下步骤-

• n：=行数，m：=列数

• 定义一个nxmx 2阶的3D数组

• dp [n-1，m-1，0] = 0，dp [n-1，m-1，1] = 1

• 对于初始化i：= m-2，当i> = 0时，更新（将i减1），执行-

• dp [n-1，i，0] = b [n-1，i]-ASCII'0'+ dp [n-1，i + 1，0]

• 如果b [n-1，i]与'X'的ASCII相同，则-

• dp [n-1，i，1] + = dp [n-1，i + 1，1]

• 对于初始化i：= n-2，当i> = 0时，更新（将i减1），执行-

• dp [i，m-1，0] = b [i，m-1]-ASCII'0'+ dp [i + 1，m-1，0]

• 如果b [i，m-1]与'X'的ASCII相同，则-

• dp [i，m-1，1] + = dp [i + 1，m-1，1]

• 对于初始化i：= n-2，当i> = 0时，更新（将i减1），执行-

• 如果b [i，j]与'X'的ASCII相同，则-

• maxVal：= {dp [i，j + 1，0]，dp [i + 1，j，0]，dp [i + 1，j + 1，0]}的最大值

• 如果maxVal等于0并且（b [i + 1，j]不等于'S'的ASCII且b [i，j + 1]不等于'S'的ASCII和b [i + 1， j + 1]不等于ASCII的“ S”），则-

• dp [i，j，0]：= dp [i，j，0] + maxVal

• 如果dp [i + 1，j，0]与maxVal相同，则-

• 如果dp [i + 1，j + 1，0]与maxVal相同，则-

• 如果dp [i，j + 1，0]与maxVal相同，则-

• dp [i，j，1]：= dp [i，j，1] mod m

• dp [i，j，0]：= dp [i，j，0] mod m

• dp [i，j，0]：=（如果b [i，j]与'E'的ASCII相同，则为0，否则b [i，j]-'0'的ASCII）

• dp [i，j，0]：= 0

• 忽略以下部分，跳至下一个迭代

• dp [i，j，1]：= dp [i，j，1] + dp [i + 1，j，1]

• dp [i，j，1]：= dp [i，j，1] + dp [i +1，j + 1，1]

• dp [i，j，1]：= dp [i，j，1] + dp [i，j + 1，1]

• 对于初始化j：= m-2，当j> = 0时，更新（将j减1），-

• 返回dp [0，0]

让我们看下面的实现以更好地理解-

示例

#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, ]