C++ এ সর্বোচ্চ স্কোর সহ পাথের সংখ্যা

ধরুন আমাদের অক্ষরের একটি বর্গাকার বোর্ড আছে। আমরা 'S' অক্ষর দিয়ে চিহ্নিত নীচের ডানদিকের বর্গক্ষেত্র থেকে শুরু করে বোর্ডে যেতে পারি। এখন আমাদের 'E' অক্ষর দিয়ে চিহ্নিত উপরের বাম বর্গক্ষেত্রে পৌঁছাতে হবে। অন্যান্য বর্গক্ষেত্রগুলি 1 থেকে 9 পর্যন্ত একটি সাংখ্যিক অক্ষর দিয়ে বা একটি বাধা 'X' দিয়ে লেবেল করা হয়। এক চালে আমরা উপরে, বাম বা উপরে-বামে যেতে পারি শুধুমাত্র যখন সেখানে কোন বাধা নেই।

আমাদের দুটি সংখ্যার তালিকা খুঁজে বের করতে হবে:প্রথম সংখ্যাটি হল সংখ্যার অক্ষরের সর্বাধিক যোগফল যা আমরা সংগ্রহ করতে পারি এবং দ্বিতীয়টি হল এই ধরনের পাথগুলির সংখ্যা যা আমরা সেই সর্বাধিক যোগফল পেতে পারি। উত্তরের জন্য এটি মডিউল 10^9 + 7 ফেরত দিন। যখন কোন পথ না থাকে, তখন [0, 0] ফেরত দিন।

সুতরাং, যদি ইনপুটটি বোর্ডের মত হয় =["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

• আরম্ভ করার জন্য 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]

  • dp[n - 1, i, 1] + =dp[n - 1, i + 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 of '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] -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' এবং b[i + 1 এর ASCII এর সমান না হয়, 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] mod m

    • dp[i, j, 0] :=dp[i, j, 0] mod 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, ]