C++ में कालकोठरी खेल

मान लीजिए कि कोई कहानी है जैसे राक्षसों ने P नाम की राजकुमारी को पकड़ लिया और उसे कालकोठरी के निचले-दाएँ कोने में कैद कर दिया। कालकोठरी में एम पंक्ति, एन कॉलम ग्रिड जैसे कमरे होते हैं। K नाम के हमारे बहादुर शूरवीर को शुरू में ऊपर-बाएँ कमरे में रखा गया था और राजकुमारी को बचाने के लिए उसे कालकोठरी से होकर लड़ना होगा।

अब शूरवीर के पास एक प्रारंभिक स्वास्थ्य बिंदु है जो एक सकारात्मक पूर्णांक द्वारा दर्शाया गया है। यदि किसी भी समय उसका स्वास्थ्य बिंदु 0 या उससे कम हो जाता है, तो उसी क्षण उसकी मृत्यु हो जाती है।

कुछ कमरों में उस कमरे की रखवाली करने के लिए राक्षस हैं, इसलिए इन कमरों में प्रवेश करने पर शूरवीर स्वास्थ्य (नकारात्मक पूर्णांक) खो देता है; अन्य कमरे या तो खाली हैं या उनमें जादू के गहने हैं जो नाइट के स्वास्थ्य को बढ़ाते हैं (सकारात्मक पूर्णांक)।

इसलिए यदि वह जल्द से जल्द राजकुमारी तक पहुंचना चाहता है, तो शूरवीर प्रत्येक चरण में केवल दाएं या नीचे की ओर बढ़ने का फैसला करता है। हमें न्यूनतम प्रारंभिक स्वास्थ्य का पता लगाना है जो P तक पहुंचने के लिए पर्याप्त होगा। इसलिए यदि इनपुट जैसा है, तो उत्तर 6 होगा, क्योंकि K, P तक पहुंच सकता है, पथ का उपयोग करके दाएं -> दाएं -> नीचे -> नीचे

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

• r :=dp की पंक्ति, c :=dp का col

• j :=r - 2 को प्रारंभ करने के लिए, जब j>=0, j को 1 से घटाएं -

  • डीपी [जे, सी -1]:=न्यूनतम डीपी [जे, सी -1] और डीपी [जे, सी -1] + डीपी [जे + 1, सी -1]

• j :=c - 2 को प्रारंभ करने के लिए, जब j>=0, j को 1 से घटाएं -

  • dp[r-1, j] :=न्यूनतम dp[r-1, j] और dp[r-1, j] + dp[r-1, j + 1]

• प्रारंभ करने के लिए i :=r - 2, जब i>=0, i को 1 से घटाएं -

  • j :=c - 2 को प्रारंभ करने के लिए, जब j>=0, j को 1 से घटाएं -

    • dp[i, j] :=न्यूनतम dp[i, j] और अधिकतम dp[i, j] + dp[i + 1, j] और dp[i, j] + dp[i, j + 1]

• अगर dp[0, 0] <=0, तो,

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