Niuke: Dragon and dungeon games

This question is an upgraded version of the maze .

We walk backwards from the end to the starting point , set up dp[i][j] For from (i,j) The minimum amount of blood to reach the end .mp Represents the value in the maze .

We need to know dp[i][j] And the one on the lower right mp,dp The relationship between .

Ideas as follows ：

We hope that one point can have as little blood as possible , That is, the minimum amount of blood to reach the destination , According to the title, the minimum blood volume is 1. Then on dp[i][j] introduce dp[i+1][j]-mp[i][j] and dp[i][j+1]-mp[i][j] Two quantities .

To sum up, these two expressions calculate the minimum value of the current node's blood volume to complete the next path , If it is negative, it means that you can complete the following path as long as the current HP is positive , We can take 1, If it is positive, it means that we need at least how much blood to ensure that we can finish the next path after walking the current point .

If the current matrix mp[i][j] It's negative , It means that you are going to lose blood , So obviously, when we came from the last point, we asked for more blood , If it comes from the left , use dp[i][j+1]-mp[i][j] You get at least the amount of blood you need to start from the point on the left （ The left side is the current point ）, This blood volume should be the same as 1 Taking the maximum , Because at least 1, Less than 1 It only shows our mp[i][j] Large enough , It may be a bloody , And if the calculated value is greater than 1 General description mp[i][j] Small enough , So we need to take a larger value to ensure that after the current point , There is still blood volume to complete the next path .

If it's going down, the idea is similar .

The following is the specific operation process ：

We start from the end , First initialize the endpoint dp[n-1][m-1]=max(1, 1-mp[n-1][m-1])

Then update each point dp[i][j]=max(1, min(dp[i+1][j], dp[i][j+1])-mp[i][j]), obviously , For the first column , The first line needs special treatment . there min Because we always require the minimum amount of blood ,max Because our blood volume is at least 1

The code is as follows ：

#include<bits/stdc++.h>
using namespace std;
//  recursive 
int solve1(int i, int j, int n, int m, vector<vector<int>> &mp, vector<vector<int>> &dp){
    if(dp[i][j]!=-1){
        return dp[i][j];
    }
    if(i==n-1 && j==m-1){
        dp[i][j]=max(1,1-mp[i][j]);    
    }else if(i==n-1){
        dp[i][j]=max(1, solve1(i, j+1, n, m, mp, dp)-mp[i][j]);
    }else if(j==m-1){
        dp[i][j]=max(1, solve1(i+1, j, n, m, mp, dp)-mp[i][j]);
    }else{
        dp[i][j]=max(1, min(solve1(i, j+1, n, m, mp, dp), solve1(i+1, j, n, m, mp, dp))-mp[i][j]);
    }
    return dp[i][j];
}
// Recurrence 
int solve2(int n,int m,vector<vector<int>> &mp, vector<vector<int>> &dp){
    dp[n-1][m-1]=max(1, 1-mp[n-1][m-1]);
    for(int i=n-2;i>=0;--i){
        dp[i][m-1]=max(1, dp[i+1][m-1]-mp[i][m-1]);
    }
    for(int j=m-2;j>=0;--j){
        dp[n-1][j]=max(1, dp[n-1][j+1]-mp[n-1][j]);
    }
    for(int i=n-2;i>=0;--i){
        for(int j=m-2;j>=0;--j){
            dp[i][j]=max(1, min(dp[i+1][j], dp[i][j+1])-mp[i][j]);
        }
    }
    return dp[0][0];
}
// Space optimization 
int solve3(int n, int m, vector<vector<int>> &mp, vector<int> &dp){
    dp[m-1]=max(1, 1-mp[n-1][m-1]);
    for(int i=m-2;i>=0;--i){
        dp[i]=max(1, dp[i+1]-mp[n-1][i]);
    }
    for(int i=n-2;i>=0;--i){
        dp[m-1]=max(1, dp[m-1]-mp[i][m-1]);
        for(int j=m-2;j>=0;--j){
            dp[j]=max(1, min(dp[j+1],dp[j])-mp[i][j]);
        }
    }
    return dp[0];
}


int main(){
    int m,n;
    cin>>n>>m;
    vector<vector<int>> mp(n, vector<int>(m));
//     vector<vector<int>> dp(n, vector<int>(m, -1));
    vector<int> dp(m);
    int res=INT_MAX;
    for(int i=0;i<m;++i){
        for(int j=0;j<n;++j){
            cin>>mp[i][j];
        }
    }
//     res=solve1(0,0,n,m,mp,dp);
//     res=solve2(n, m, mp, dp);
    res=solve3(n, m, mp, dp);
    cout<<res<<endl;
    return 0;
}

This is the inspiration brought to me by a problem solving of Niuke network ~