C++ में अधिकतम स्कोर वाले पथों की संख्या

मान लीजिए कि हमारे पास वर्णों का एक वर्गाकार बोर्ड है। हम अक्षर 'S' के साथ चिह्नित निचले दाएं वर्ग से शुरू होने वाले बोर्ड पर जा सकते हैं। अब हमें अक्षर 'ई' के साथ चिह्नित ऊपरी बाएँ वर्ग तक पहुँचने की आवश्यकता है। अन्य वर्गों को या तो 1 से 9 तक अंकीय वर्ण या बाधा 'X' के साथ लेबल किया जाता है। एक चाल में हम ऊपर, बाएँ या ऊपर-बाएँ तभी जा सकते हैं जब वहाँ कोई बाधा न हो।

हमें दो संख्याओं की सूची ढूंढ़नी है:पहली संख्या हमारे द्वारा एकत्रित किए जा सकने वाले संख्यात्मक वर्णों का अधिकतम योग है, और दूसरी संख्या ऐसे पथों की संख्या है जिन्हें हम अधिकतम योग प्राप्त करने के लिए ले सकते हैं। उत्तर के लिए इसे मॉड्यूलो 10^9 + 7 लौटाएं। जब कोई रास्ता नहीं है, तो वापस लौटें [0, 0]।

इसलिए, यदि इनपुट बोर्ड =["E12", "1X1", "21S"] जैसा है, तो आउटपुट [1,2]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=पंक्तियों की संख्या, m :=स्तंभों की संख्या

• क्रम n x m x 2 के एक 3D सरणी को परिभाषित करें

• डीपी [एन - 1, एम - 1, 0] =0, डीपी [एन - 1, एम - 1, 1] =1

• प्रारंभ करने के लिए i :=m - 2, जब i>=0, अद्यतन करें (i से 1 घटाएं), करें -

  • यदि b[n-1, i] 'X' के ASCII के समान है, तो -

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

  • डीपी [एन -1, आई, 1] + =डीपी [एन -1, आई + 1, 1]

• इनिशियलाइज़ करने के लिए i :=n - 2, जब i>=0, अपडेट करें (i से 1 घटाएं), −

  करें

  • यदि b[i, m - 1] 'X' के ASCII के समान है, तो -

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

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

• इनिशियलाइज़ करने के लिए 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] -'0' का 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] 'S' के ASCII के बराबर नहीं है), तो -

      • डीपी [i, जे, 0]:=0

      • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

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

    • अगर dp[i + 1, j, 0] मैक्सवैल के समान है, तो -

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

    • अगर dp[i + 1, j + 1, 0] मैक्सवैल के समान है, तो -

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

    • अगर dp[i, j + 1, 0] मैक्सवैल के समान है, तो -

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

    • डीपी [आई, जे, 1]:=डीपी [आई, जे, 1] मॉड एम

    • डीपी [i, j, 0]:=dp [i, j, 0] मॉड m

• वापसी डीपी [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, ]