সি++ এ অন্ধকূপ গেম

ধরুন এমন একটি গল্প আছে যেমন রাক্ষসরা রাজকন্যাকে ধরে নিয়েছিল যার নাম পি এবং তাকে একটি অন্ধকূপের নীচে-ডানদিকে বন্দী করেছিল৷ অন্ধকূপটি M সারি, N কলাম গ্রিডের মতো কক্ষ নিয়ে গঠিত। কে নামের আমাদের বীর নাইটকে প্রথমে উপরের-বাম ঘরে অবস্থান করা হয়েছিল এবং রাজকন্যাকে উদ্ধার করতে অন্ধকূপের মধ্য দিয়ে লড়াই করতে হবে।

এখন নাইটের একটি প্রাথমিক স্বাস্থ্য বিন্দু রয়েছে যা একটি ধনাত্মক পূর্ণসংখ্যা দ্বারা উপস্থাপিত হয়। যে কোনো সময়ে যদি তার স্বাস্থ্যের পয়েন্ট 0 বা তার নিচে নেমে যায়, সেই মুহূর্তে সে মারা যায়।

কিছু কক্ষে সেই ঘরটি পাহারা দেওয়ার জন্য ভূত থাকে, তাই এই কক্ষে প্রবেশ করার পরে নাইট স্বাস্থ্য (ঋণাত্মক পূর্ণসংখ্যা) হারায়; অন্যান্য কক্ষগুলি হয় খালি অথবা এতে যাদুকক্ষ রয়েছে যা নাইটের স্বাস্থ্য বৃদ্ধি করে (ধনাত্মক পূর্ণসংখ্যা)।

তাই যদি সে যত তাড়াতাড়ি সম্ভব রাজকন্যার কাছে পৌঁছতে চায়, নাইট সিদ্ধান্ত নেয় প্রতিটি ধাপে ডানদিকে বা নীচের দিকে সরে যাবে। আমাদের ন্যূনতম প্রারম্ভিক স্বাস্থ্য খুঁজে বের করতে হবে যা P-তে পৌঁছানোর জন্য যথেষ্ট হবে। তাই যদি ইনপুটটি হয়, তাহলে উত্তর হবে 6, কারণ K রাইট -> রাইট -> ডাউন -> ডাউন পথ ব্যবহার করে P-তে পৌঁছাতে পারে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• r :=dp-এর সারি, c :=dp-এর col

• j শুরু করার জন্য :=r - 2, যখন j>=0, j কমিয়ে 1 do −

  • dp[j, c - 1] :=ন্যূনতম dp[j, c - 1] এবং dp[j, c - 1] + dp[j + 1, c - 1]

• j শুরু করার জন্য :=c - 2, যখন j>=0, j কমিয়ে 1 do −

  • dp[r - 1, j] :=ন্যূনতম dp[r - 1, j] এবং dp[r - 1, j] + dp[r - 1, j + 1]

• শুরু করার জন্য i :=r - 2, যখন i>=0, i 1 do −

  • j শুরু করার জন্য :=c - 2, যখন j>=0, j কমিয়ে 1 do −

    • dp[i, j] :=সর্বনিম্ন dp[i, j] এবং সর্বাধিক dp[i, j] + dp[i + 1, j] এবং dp[i, j] + dp[i, j + 1]

• যদি dp[0, 0] <=0, তারপর,

  • ফেরত |dp[0, 0]| + 1

• রিটার্ন 1

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli min(lli a, lli b){
   return a <= b ? a : b;
}
lli max(lli a, lli b){
   return a <= b ? b : a;
}
class Solution {
public:
   int calculateMinimumHP(vector<vector<int>>& dp) {
      int r = dp.size();
      int c = dp[0].size();
      for(lli j=r-2;j>=0;j--){
         dp[j][c-1] = min(dp[j][c-1], dp[j][c-1]+dp[j+1][c-1]);
      }
      for(lli j = c-2;j>=0;j--){
         dp[r-1][j] =min(dp[r-1][j], dp[r-1][j]+dp[r-1][j+1]);
      }
      for(lli i = r-2;i>=0;i--){
         for(lli j = c-2;j>=0;j--){
            dp[i][j] = min(dp[i][j],max(dp[i][j]+dp[i+1][j],dp[i][j]+dp[i][j+1]));
         }
      }
      if(dp[0][0] <= 0 )return abs(dp[0][0])+1;
      return 1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{-2,-2,3},{-5,-10,1},{10,30,-5}};
   cout << (ob.calculateMinimumHP(v));
}

ইনপুট

{{-2,-2,3},{-5,-10,1},{10,30,-5}}

আউটপুট

6