เกมดันเจี้ยนใน C++

สมมุติว่ามีเรื่องราวเหมือนปีศาจจับเจ้าหญิงที่ชื่อ P และขังเธอไว้ที่มุมล่างขวาของคุกใต้ดิน ดันเจี้ยนประกอบด้วยห้องแถว M, ห้องเหมือนตาราง N คอลัมน์ อัศวินผู้กล้าหาญของเราชื่อ K อยู่ในห้องซ้ายบนสุดในตอนแรก และต้องต่อสู้ฝ่าดันเจี้ยนเพื่อช่วยเจ้าหญิง

ตอนนี้อัศวินมีคะแนนสุขภาพเริ่มต้นที่แสดงด้วยจำนวนเต็มบวก หากแต้มสุขภาพของเขาลดลงเหลือ 0 หรือต่ำกว่า เขาจะเสียชีวิตในขณะนั้น

บางห้องมีปีศาจคอยปกป้องห้องนั้น ดังนั้นอัศวินจะสูญเสียสุขภาพ (จำนวนเต็มลบ) เมื่อเข้ามาในห้องเหล่านี้ ห้องอื่นว่างหรือมีลูกแก้ววิเศษที่ช่วยเพิ่มสุขภาพของอัศวิน (จำนวนเต็มบวก)

ดังนั้น ถ้าเขาต้องการไปถึงเจ้าหญิงโดยเร็วที่สุด อัศวินก็ตัดสินใจเคลื่อนไปทางขวาหรือลงในแต่ละขั้นตอนเท่านั้น เราต้องหาสุขภาพเริ่มต้นขั้นต่ำที่จะเพียงพอที่จะไปถึง P ดังนั้นหากอินพุตเป็นเช่นนั้นคำตอบจะเป็น 6 เนื่องจาก K สามารถเข้าถึง P โดยใช้เส้นทาง Right -> Right -> Down -> Down

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• r :=แถวของ dp, c :=col ของ 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, ลดลง 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 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;} โซลูชันคลาส {สาธารณะ:int คำนวณMinimumHP (เวกเตอร์<เวกเตอร์>&dp) { int r =dp.size (); int c =dp[0].size(); สำหรับ(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]); } สำหรับ(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--){ สำหรับ(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; ส่งคืน 1; }};main(){ โซลูชัน ob; เวกเตอร์<เวกเตอร์> v ={{-2,-2,3},{-5,-10,1},{10,30,-5}}; cout <<(ob.calculateMinimumHP(v));}

อินพุต

ผลลัพธ์

6