C++ में डंजिओन गेम

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

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

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

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

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

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

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

  • dp[j, c - 1] := dp[j, c - 1] और dp[j, c - 1] + dp[j + 1, c - 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, तो,

  • |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