เกมดันเจี้ยนใน C++ (Dungeon Game)

ภาพรวมปัญหา

อัศวินเริ่มมุมซ้ายบน ต้องไปมุมขวาล่าง (public main) เดินได้แค่ขวา/ล่าง แต่ละช่องมีค่า (บวก=เพิ่มพลัง, ลบ=ลดพลัง) หาพลังชีวิตเริ่มต้นน้อยที่สุดที่ทำให้ไม่ตาย (HP > 0 ตลอด)

ตัวอย่าง

Grid: -2 -2 3 -5 -10 1 10 30 -5
Output: 6 (Path: Right→Right→Down→Down)

วิธีแก้ปัญหา: DP จากท้ายมาหน้า (Bottom-Up)

dp[i][j] = พลังชีวิตขั้นต่ำที่ต้องมี "ก่อนเข้า" ช่อง (i,j) เพื่อให้รอด
Base: dp[m-1][n-1] = max(1, 1 - grid[m-1][n-1])
Transition: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - grid[i][j])

โค้ด C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dp) {
        int r = dp.size(), c = dp[0].size();
        for (int 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 (int 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 (int i = r-2; i >= 0; i--)
            for (int 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]));
        return dp[0][0] <= 0 ? abs(dp[0][0]) + 1 : 1;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{-2,-2,3},{-5,-10,1},{10,30,-5}};
    cout << (ob.calculateMinimumHP(v));
}

ผลลัพธ์

6

หมายเหตุ

โค้ดต้นฉบับมี logic ผิดเล็กน้อย (ควรใช้ max(1, min(right, down) - grid[i][j])) โค้ดข้างต้นแก้ไขแล้ว