[Swift]LeetCode174. 地下城游戏 | Dungeon Game
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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.
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
| -2 (K) | -3 | 3 |
| -5 | -10 | 1 |
| 10 | 30 | -5 (P) |
说明:
骑士的健康点数没有上限。
- 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
56ms
1 class Solution {
2 func calculateMinimumHP(_ dungeon: [[Int]]) -> Int {
3 var m:Int = dungeon.count
4 var n:Int = dungeon[0].count
5 var dp:[Int] = [Int](repeating:Int.max,count:n + 1)
6 dp[n - 1] = 1
7 for i in (0..<m).reversed()
8 {
9 for j in (0..<n).reversed()
10 {
11 dp[j] = max(1, min(dp[j], dp[j + 1]) - dungeon[i][j])
12 }
13 }
14 return dp[0]
15 }
16 }60ms
1 class Solution {
2
3 func calculateMinimumHP(_ dungeon: [[Int]]) -> Int {
4 let n = dungeon.count
5 if n > 0 {
6 let m = dungeon[0].count
7 var c = [[Int]](repeating:[Int](repeating: .max, count: m + 1), count: n + 1)
8 c[n][m-1] = 0
9 c[n-1][m] = 0
10 for i in stride(from: n-1, through: 0, by: -1) {
11 for j in stride(from: m-1, through: 0, by: -1) {
12 let next = min(c[i+1][j],c[i][j+1])
13 var cur = -dungeon[i][j] + next
14 cur = max(cur, 0)
15 c[i][j] = cur
16 }
17 }
18 return c[0][0] + 1
19 } else {
20 return 1
21 }
22 }
23 }60ms
1 class Solution {
2 func calculateMinimumHP(_ dungeon: [[Int]]) -> Int {
3
4 let m = dungeon.count
5 let n = dungeon[0].count
6
7 var dp = Array(repeating: Array(repeating: 0, count: n), count: m)
8
9 dp [m-1][n-1] = dungeon[m-1][n-1] < 0 ? -1 * dungeon[m-1][n-1] + 1 : 1
10 for i in stride(from: m-2, to: -1, by: -1) {
11 dp[i][n-1] = max(dp[i+1][n-1] - dungeon[i][n-1] , 1)
12 }
13 for j in stride(from: n-2, to: -1, by: -1) {
14 dp[m-1][j] = max(dp[m-1][j+1] - dungeon[m-1][j], 1)
15 }
16
17 for i in stride(from: m-2, to: -1, by: -1) {
18 for j in stride(from: n-2, to: -1, by: -1) {
19 let minIJ = min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j]
20 dp[i][j] = max(minIJ, 1)
21 }
22 }
23
24 return dp[0][0]
25 }
26 }68ms
1 class Solution {
2 func calculateMinimumHP(_ dungeon: [[Int]]) -> Int {
3 let rows = dungeon.count
4 let cols = dungeon[0].count
5 var dp = Array(repeating: Array(repeating: Int.max, count: cols + 1), count: rows + 1)
6
7 dp[rows][cols - 1] = 1
8 dp[rows - 1][cols] = 1
9
10 for i in stride(from: rows - 1, to: -1, by: -1 ) {
11 for j in stride(from: cols - 1, to: -1, by: -1 ) {
12 let mv = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
13 dp[i][j] = mv <= 0 ? 1 : mv
14 }
15 }
16 print(dp)
17 return dp[0][0]
18 }
19 }80ms
1 class Solution {
2 var result: [[Int]]!
3 var flag: [[Bool]]!
4 func calculateMinimumHP(_ dungeon: [[Int]]) -> Int {
5 let row = dungeon.count
6 let column = dungeon.first!.count
7 result = Array(repeatElement(Array(repeatElement(0, count: column)), count: row))
8 flag = Array(repeatElement(Array(repeatElement(false, count: column)), count: row))
9 flag[row - 1][column - 1] = true
10 result[row - 1][column - 1] = dungeon[row - 1][column - 1]
11
12 let answer = calculateResult(dungeon)
13 return answer <= 0 ? 1 - answer : 1
14 }
15
16 func calculateResult(_ dungeon: [[Int]], _ n: Int = 0, _ m: Int = 0) -> Int {
17 if n == dungeon.count || m == dungeon.first!.count {
18 return -Int.max
19 }
20 if flag[n][m] == false {
21 flag[n][m] = true
22 result[n][m] = dungeon[n][m] + max(min(0, calculateResult(dungeon, n, m + 1)),
23 min(0, calculateResult(dungeon, n + 1, m)))
24 }
25 return result[n][m]
26 }
27 }