diff options
author | Jack Sangdahl <[email protected]> | 2024-11-29 12:57:10 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-11-29 12:57:10 -0700 |
commit | a78731d3c5187a32ac47a476baa41396f1524af3 (patch) | |
tree | 745dab5a30edb139ae528b7cbc0b3e21fc31dd36 | |
parent | 4e7f851984f894d78ebb75465b60989967e3421a (diff) | |
download | leetcode-a78731d3c5187a32ac47a476baa41396f1524af3.tar.gz leetcode-a78731d3c5187a32ac47a476baa41396f1524af3.zip |
174. dungeon game
-rw-r--r-- | dungeon_game.c | 50 | ||||
-rw-r--r-- | dungeon_game.py | 32 |
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]])) |