C++의 던전 게임

P라는 이름의 공주를 악마가 붙잡아 던전의 오른쪽 하단에 가둔 것과 같은 이야기가 있다고 가정해 봅시다. 던전은 M행 N열 격자 형태의 방으로 구성되어 있습니다. K라는 이름의 용감한 기사는 처음에 왼쪽 상단 방에 배치되었으며 공주를 구출하기 위해 던전을 통해 싸워야 합니다.

이제 기사는 양의 정수로 표시되는 초기 체력을 가집니다. 어느 시점에서 그의 건강 포인트가 0 이하로 떨어지면 그 순간에 사망합니다.

일부 방에는 그 방을 지키는 악마가 있으므로 기사는 이 방에 들어갈 때 건강(음의 정수)을 잃습니다. 다른 방은 비어 있거나 기사의 건강을 증가시키는 마법의 구를 포함합니다(양의 정수).

그래서 가능한 한 빨리 공주에게 다가가고 싶다면 기사는 각 단계에서 오른쪽 또는 아래쪽으로만 이동하기로 결정합니다. 우리는 P에 도달하기에 충분한 최소 초기 상태를 찾아야 합니다. 따라서 입력이 다음과 같으면 오른쪽 -> 오른쪽 -> 아래쪽 -> 아래쪽 경로를 사용하여 K가 P에 도달할 수 있으므로 답은 6이 됩니다.

-2(k)	-2	3
-5	-10	1
10	30	-5p

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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

C++의 던전 게임

예시

입력

출력