题解 | 龙与地下城游戏问题

暴力算法 遍历每一条路记录最小血量

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int n,m;
vector<int> dp;

void solve(vector<vector<int>> &map, int x, int y, int last, int min_step)
{
    if(x == n - 1 && y == m-1)
    {
        dp.push_back(min(min_step, map[x][y]+last));
        return;
    }
    int current = map[x][y]+last;
    if(x<n -1 )
    {
        solve(map, x+1, y, current, min(min_step, current));
    }

    if(y<m -1)
    {
        solve(map, x, y+1, current, min(min_step, current));
    }
}

int main() {
    cin >> n >> m;
    vector<vector<int>> map(n,vector<int>(m,0));
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin>>map[i][j];
        }
    }
    solve(map, 0,0,0,map[0][0]);
    sort(dp.begin(), dp.end());
    if(dp.back()>=1)
    {
        cout<<1;
    }
    else {
        cout<<1-dp.back();
    }
    return 0;
}