C++のダンジョンゲーム

悪魔がPという名前の王女を捕まえて、ダンジョンの右下隅に閉じ込めたような話があるとします。ダンジョンは、M列、N列のグリッドのような部屋で構成されています。 Kという名前の勇敢な騎士は、最初は左上の部屋に配置されていたため、王女を救出するためにダンジョンを通り抜ける必要があります。

これで、騎士は正の整数で表される初期ヘルスポイントを持ちます。いずれかの時点で彼のヘルスポイントが0以下に下がると、彼はその瞬間に死亡します。

一部の部屋にはその部屋を守るための悪魔がいるため、騎士はこれらの部屋に入ると体力を失います（負の整数）。他の部屋は空であるか、騎士の健康を増進する魔法の球を含んでいます（正の整数）。

したがって、彼ができるだけ早く王女に到達したい場合、騎士は各ステップで右または下にのみ移動することを決定します。 Pに到達するのに十分な最小の初期ヘルスを見つける必要があります。したがって、入力がのような場合、KはパスRight-> Right-> Down-> Downを使用してPに到達できるため、答えは6になります。

これを解決するには、次の手順に従います-

• r：=dpの行、c：=dpの列

• 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