C++에서 최대 점수가 있는 경로 수

사각형 문자 보드가 있다고 가정해 보겠습니다. 우리는 문자 'S'로 표시된 오른쪽 하단 사각형에서 시작하여 보드에서 이동할 수 있습니다. 이제 'E' 문자가 표시된 왼쪽 상단 사각형에 도달해야 합니다. 다른 사각형은 1에서 9까지의 숫자 또는 장애물 'X'로 레이블이 지정됩니다. 한 번의 이동으로 장애물이 없을 때만 위, 왼쪽 또는 위 왼쪽으로 이동할 수 있습니다.

우리는 두 개의 숫자 목록을 찾아야 합니다. 첫 번째 숫자는 수집할 수 있는 숫자의 최대 합이고 두 번째 숫자는 최대 합을 얻기 위해 취할 수 있는 경로의 수입니다. 답은 모듈로 10^9 + 7을 반환합니다. 경로가 없으면 [0, 0]을 반환합니다.

따라서 입력이 board =["E12","1X1","21S"]와 같으면 출력은 [1,2]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=행 수, m :=열 수

• n x m x 2 차수의 3D 배열을 정의합니다.

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

• initialize i :=m - 2의 경우 i>=0일 때 업데이트(i를 1만큼 감소), −

  • b[n - 1, i]가 'X'의 ASCII와 같으면 -

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

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

• initialize i :=n - 2의 경우 i>=0일 때 업데이트(i를 1만큼 감소), −

  • b[i, m - 1]이 'X'의 ASCII와 같으면 -

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

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

• initialize i :=n - 2의 경우 i>=0일 때 업데이트(i를 1만큼 감소), −

  • 초기화 j :=m - 2의 경우 j>=0일 때 업데이트(j를 1만큼 감소), −

    • b[i, j]가 'X'의 ASCII와 같으면 -

      • dp[i, j, 0] :=(b[i, j]가 'E'의 ASCII와 같으면 0, 그렇지 않으면 b[i, j] -ASCII '0')

    • 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]은 'S'의 ASCII와 같지 않음), −

      • dp[i, j, 0] :=0

      • 다음 부분은 무시하고 다음 반복으로 건너뜁니다.

    • dp[i, j, 0] :=dp[i, j, 0] + maxVal

    • dp[i + 1, j, 0]이 maxVal과 같으면 -

      • dp[i, j, 1] :=dp[i, j, 1] + dp[i + 1, j, 1]

    • dp[i + 1, j + 1, 0]이 maxVal과 같으면 -

      • dp[i, j, 1] :=dp[i, j, 1] + dp[i + 1, j + 1, 1]

    • dp[i, j + 1, 0]이 maxVal과 같으면 -

      • dp[i, j, 1] :=dp[i, j, 1] + dp[i, j + 1, 1]

    • dp[i, j, 1] :=dp[i, j, 1] 모드 m

    • dp[i, j, 0] :=dp[i, j, 0] 모드 m

• 반환 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, ]