aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-29 12:57:10 -0700
committerJack Sangdahl <[email protected]>2024-11-29 12:57:10 -0700
commita78731d3c5187a32ac47a476baa41396f1524af3 (patch)
tree745dab5a30edb139ae528b7cbc0b3e21fc31dd36
parent4e7f851984f894d78ebb75465b60989967e3421a (diff)
downloadleetcode-a78731d3c5187a32ac47a476baa41396f1524af3.tar.gz
leetcode-a78731d3c5187a32ac47a476baa41396f1524af3.zip
174. dungeon game
-rw-r--r--dungeon_game.c50
-rw-r--r--dungeon_game.py32
2 files changed, 82 insertions, 0 deletions
diff --git a/dungeon_game.c b/dungeon_game.c
new file mode 100644
index 0000000..6a54e5d
--- /dev/null
+++ b/dungeon_game.c
@@ -0,0 +1,50 @@
+// 174. Dungeon Game
+#include "leetcode.h"
+
+/*
+ * the demons had captured the princess 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 was initially positioned in the top left room and
+ * must fight his way through the 'dungeon' to rescue the princess. return the
+ * knight's minimum initial health so that he can rescue the princess. note that
+ * any romm can contain threats or power ups even the first room the knight
+ * enters and the bottom right room where the princess is imprisoned
+ */
+
+int calculateMinimumHP(int **dungeon, int dungeonSize, int *dungeonColSize) {
+ int m = dungeonSize, n = *dungeonColSize;
+ int **dp = (int **)malloc(m * sizeof(int *));
+ for (int i = 0; i < m; i++)
+ dp[i] = (int *)malloc(n * sizeof(int));
+ for (int i = m - 1; i >= 0; i--)
+ for (int j = n - 1; j >= 0; j--) {
+ if (i == m - 1 && j == n - 1)
+ dp[i][j] = 1;
+ else if (i == m - 1)
+ dp[i][j] = dp[i][j + 1] - dungeon[i][j + 1];
+ else if (j == n - 1)
+ dp[i][j] = dp[i + 1][j] - dungeon[i + 1][j];
+ else
+ dp[i][j] = fmin(dp[i][j + 1] - dungeon[i][j + 1],
+ dp[i + 1][j] - dungeon[i + 1][j]);
+ dp[i][j] = fmax(1, dp[i][j]);
+ }
+ int ans = dp[0][0] - dungeon[0][0];
+ for (int i = 0; i < m; i++)
+ free(dp[i]);
+ free(dp);
+ return ans;
+}
+
+int main() {
+ int d1i[3][3] = {{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}}, d2i[1][1] = {{0}};
+ struct two_d_arr d1, d2;
+ two_d_arr_init(&d1, 3, 3, d1i);
+ two_d_arr_init(&d2, 1, 1, d2i);
+ printf("%d\n",
+ calculateMinimumHP(d1.arr, d1.row_size, d1.col_size)); // expect: 7
+ printf("%d\n",
+ calculateMinimumHP(d2.arr, d2.row_size, d2.col_size)); // expect: 1
+ two_d_arr_free(&d1);
+ two_d_arr_free(&d2);
+}
diff --git a/dungeon_game.py b/dungeon_game.py
new file mode 100644
index 0000000..bf96d4b
--- /dev/null
+++ b/dungeon_game.py
@@ -0,0 +1,32 @@
+# 174. Dungeon Game
+
+"""
+the demons had captured the princess 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 was initially positioned in the top left room and
+must fight his way through the 'dungeon' to rescue the princess. return the
+knight's minimum initial health so that he can rescue the princess. note that
+any romm can contain threats or power ups even the first room the knight
+enters and the bottom right room where the princess is imprisoned
+"""
+
+
+class Solution(object):
+ def calculateMinimumHP(self, dungeon):
+ """
+ :type dungeon: List[List[int]]
+ :rtype: int
+ """
+ m, n = len(dungeon), len(dungeon[0])
+ dp = [[float("inf")] * (n + 1) for _ in range(m + 1)]
+ dp[m - 1][n], dp[m][n - 1] = 1, 1
+ for i in range(m - 1, -1, -1):
+ for j in range(n - 1, -1, -1):
+ dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j], 1)
+ return dp[0][0]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.calculateMinimumHP(dungeon=[[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]))
+ print(obj.calculateMinimumHP(dungeon=[[0]]))