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