Computer >> Máy Tính >  >> Lập trình >> C ++

Game Dungeon trong C ++

Giả sử có một câu chuyện như thể những con quỷ đã bắt công chúa tên P và giam cô ấy ở góc dưới bên phải của ngục tối. Hầm ngục bao gồm M hàng, N cột phòng giống như lưới. Hiệp sĩ dũng cảm tên K của chúng ta ban đầu được bố trí ở căn phòng trên cùng bên trái và phải chiến đấu vượt qua ngục tối để giải cứu công chúa.

Bây giờ hiệp sĩ có điểm sức khỏe ban đầu được biểu thị bằng một số nguyên dương. Nếu tại bất kỳ thời điểm nào điểm máu của anh ta giảm xuống 0 hoặc thấp hơn, anh ta sẽ chết ngay tại thời điểm đó.

Một số căn phòng có ma quỷ canh giữ căn phòng đó, vì vậy hiệp sĩ bị mất sức khỏe (số nguyên âm) khi vào những căn phòng này; các phòng khác trống hoặc chứa các quả cầu ma thuật giúp tăng lượng máu của hiệp sĩ (số nguyên dương).

Vì vậy, nếu anh ta muốn tiếp cận công chúa càng nhanh càng tốt, hiệp sĩ quyết định chỉ di chuyển sang phải hoặc đi xuống trong mỗi bước. Chúng ta phải tìm sức khỏe ban đầu tối thiểu đủ để đến P. Vì vậy, nếu đầu vào là như thế, thì câu trả lời sẽ là 6, vì K có thể đến P, sử dụng con đường Right -> Right -> Down -> Down

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

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

  • r:=row of dp, c:=col of dp

  • để khởi tạo j:=r - 2, khi j> =0, giảm j đi 1 do -

    • dp [j, c - 1]:=tối thiểu của dp [j, c - 1] và dp [j, c - 1] + dp [j + 1, c - 1]

  • để khởi tạo j:=c - 2, khi j> =0, giảm j đi 1 do -

    • dp [r - 1, j]:=tối thiểu của dp [r - 1, j] và dp [r - 1, j] + dp [r - 1, j + 1]

  • để khởi tạo i:=r - 2, khi i> =0, giảm i đi 1 do -

    • để khởi tạo j:=c - 2, khi j> =0, giảm j đi 1 do -

      • dp [i, j]:=tối thiểu là dp [i, j] và tối đa là dp [i, j] + dp [i + 1, j] và dp [i, j] + dp [i, j + 1]

  • nếu dp [0, 0] <=0, thì

    • trả về | dp [0, 0] | + 1

  • trả lại 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

#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));
}

Đầu vào 

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

Đầu ra 

6