Leetcode#174 Dungeon Game

原题地址

典型的地图寻路问题

如何计算当前位置最少需要多少体力呢?无非就是在向下走或向右走两个方案里做出选择罢了。

如果向下走,看看当前位置能提供多少体力(如果是恶魔就是负数,如果是草药就是正数),如果当前位置能够提供的体力比向下走所需要的最小体力还多,那么当前位置只需要1的体力就够了;否则,计算出额外需要多少体力。

如果向右走,同理。

设任意坐标(i, j)处最少需要health[i][j]的体力才能通关,则有如下递推公式:

health[i][j] = min{
dungeon[i][j] >= health[i+1][j] ? 1 : health[i+1][j] - dungeon[i][j],
dungeon[i][j] >= health[i][j+1] ? 1 : health[i][j+1] - dungeon[i][j]
}

因为递推公式只用到了相邻层,所以可以在编码时压缩成1维数组节省空间。

代码:

 int calculateMinimumHP(vector<vector<int> > &dungeon) {
if (dungeon.empty() || dungeon[].empty()) return -; int m = dungeon.size();
int n = dungeon[].size();
vector<int> health(n, ); health[n - ] = dungeon[m - ][n - ] >= ? : - dungeon[m - ][n - ]; for (int j = n - ; j >= ; j--)
health[j] = dungeon[m - ][j] >= health[j + ] ? : health[j + ] - dungeon[m - ][j]; for (int i = m - ; i >= ; i--) {
health[n - ] = dungeon[i][n - ] >= health[n - ] ? : health[n - ] - dungeon[i][n - ];
for (int j = n - ; j >= ; j--) {
int right = dungeon[i][j] >= health[j + ] ? : health[j + ] - dungeon[i][j];
int down = dungeon[i][j] >= health[j] ? : health[j] - dungeon[i][j];
health[j] = min(right, down);
}
} return health[];
}
上一篇:收集的一些jQuery (我平常用的少的,但确实挺有效果的)


下一篇:oracle12c(oracle12.1.0.1.0)安装指南--实测OEL5.9(RH5)