/*
* @lc app=leetcode id=174 lang=cpp
*
* [174] Dungeon Game
*
* https://leetcode.com/problems/dungeon-game/description/
*
* algorithms
* Hard (26.59%)
* Total Accepted: 64.1K
* Total Submissions: 239.1K
* Testcase Example: '[[-2,-3,3],[-5,-10,1],[10,30,-5]]'
*
* table.dungeon, .dungeon th, .dungeon td {
* border:3px solid black;
* }
*
* .dungeon th, .dungeon td {
* text-align: center;
* height: 70px;
* 70px;
* }
*
* The demons had captured the princess (P) and imprisoned her in the
* bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid
* out in a 2D grid. Our valiant knight (K) was initially positioned in the
* top-left room and must fight his way through the dungeon to rescue the
* princess.
*
* The knight has an initial health point represented by a positive integer. If
* at any point his health point drops to 0 or below, he dies immediately.
*
* Some of the rooms are guarded by demons, so the knight loses health
* (negative integers) upon entering these rooms; other rooms are either empty
* (0's) or contain magic orbs that increase the knight's health (positive
* integers).
*
* In order to reach the princess as quickly as possible, the knight decides to
* move only rightward or downward in each step.
*
*
*
* Write a function to determine the knight's minimum initial health so that he
* is able to rescue the princess.
*
* For example, given the dungeon below, the initial health of the knight must
* be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN ->
* DOWN.
*
*
*
*
* -2 (K)
* -3
* 3
*
*
* -5
* -10
* 1
*
*
* 10
* 30
* -5 (P)
*
*
*
*
*
*
* Note:
*
*
* The knight's health has no upper bound.
* Any room can contain threats or power-ups, even the first room the knight
* enters and the bottom-right room where the princess is imprisoned.
*
*
*/
#include<vector>
#include<iostream>
#include<cmath>
#include<limits.h>
#define min(a,b) (a>b?b:a)
#define max(a,b) (a<b?b:a)
class Solution {
public:
int calculateMinimumHP(std::vector<std::vector<int>>& dungeon) {
int minHP = INT_MIN;
int row = dungeon.size();
int col = dungeon[0].size();
int tmp;
std::vector<std::vector<int>> mem(row,std::vector<int>(col));
mem[row-1][col-1] = dungeon[row-1][col-1]<0 ? dungeon[row-1][col-1] : 0;
for(int i = row -2;i >= 0; --i){
mem[i][col-1] = dungeon[i][col-1] > 0 ? min(dungeon[i][col-1]+ mem[i+1][col-1],0) : dungeon[i][col-1]+ mem[i+1][col-1];
}
for(int j = col - 2;j >=0 ; --j){
mem[row - 1][j] = dungeon[row-1][j] > 0 ? min(dungeon[row-1][j] + mem[row-1][j+1],0) : dungeon[row-1][j] + mem[row-1][j+1];
}
for(int i = row - 2;i >= 0; --i){
for(int j = col - 2;j >= 0; --j){
mem[i][j] = dungeon[i][j] > 0 ?
min(max(mem[i+1][j], mem[i][j+1]) + dungeon[i][j],0) :
max( mem[i+1][j] , mem[i][j+1] ) + dungeon[i][j];
}
// minHP = dungeon[i][j];
}
// for(int i = 0;i < row;++i){
// for(int j = 0;j<col;++j){
// std::cout<<mem[i][j]<<' ';
// }
// std::cout<<std::endl;
// }
return -mem[0][0] + 1;
}
};
int main()
{
Solution s;
std::vector<std::vector<int>> tmp = {{1,-4,5,-99},{2,-2,-2,-1}};
std::cout<<s.calculateMinimumHP(tmp)<<std::endl;
return 0;
}
主要存在的问题，这里一定要明确的一点是，我们从左上角出发，前进过程中，每一个格子的最小生命值是由后面的路径所决定的，因此，不能从左上角开始规划，要从右下角开始；
二是在前进过程中，每一个点的最小生命值是由之后的最小生命值和当前的格子决定的，并且需要比较右和坐两个方向。
class Solution {
public:
int calculateMinimumHP(std::vector<std::vector<int>>& dungeon) {
int minHP = INT_MIN;
int row = dungeon.size();
int col = dungeon[0].size();
int tmp;
if(dungeon[row-1][col-1]>0) dungeon[row-1][col-1] = 0;
//the last col
for(int i = row -2;i >= 0; --i){
dungeon[i][col-1] = dungeon[i][col-1] > 0 ? min(dungeon[i][col-1]+ dungeon[i+1][col-1],0) : dungeon[i][col-1]+ dungeon[i+1][col-1];
}
// printVectorInt(dungeon);
//the last row
for(int j = col - 2;j >=0 ; --j){
dungeon[row - 1][j] = dungeon[row-1][j] > 0 ? min(dungeon[row-1][j] + dungeon[row-1][j+1],0) : dungeon[row-1][j] + dungeon[row-1][j+1];
}
// printVectorInt(dungeon);
for(int i = row - 2;i >= 0; --i){
for(int j = col - 2;j >= 0; --j){
dungeon[i][j] = dungeon[i][j] > 0 ?
min(max(dungeon[i+1][j], dungeon[i][j+1]) + dungeon[i][j],0) :
max( dungeon[i+1][j] , dungeon[i][j+1] ) + dungeon[i][j];
}
// minHP = dungeon[i][j];
}
// printVectorInt(dungeon);
return -dungeon[0][0] + 1;
}
void printVectorInt(std::vector<std::vector<int>>& dungeon){
int row = dungeon.size();
int col = dungeon[0].size();
for(int i = 0;i < row;++i){
for(int j = 0;j<col;++j){
std::cout<<dungeon[i][j]<<' ';
}
std::cout<<std::endl;
}
}
};
在原数组上操作，能减少一点内存，但效果不明显。
