dungeon_game

hitzzc · hitzzc · commit 440e80e3f2a4 · 2016-10-15T22:32:15.000+08:00
diff --git a/README.md b/README.md
@@ -150,6 +150,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [171. Excel Sheet Column Number](https://github.com/hitzzc/go-leetcode/tree/master/excel_sheet_column_number)
 #### [172. Factorial Trailing Zeroes](https://github.com/hitzzc/go-leetcode/tree/master/factorial_trailing_zeroes)
 #### [173. Binary Search Tree Iterator](https://github.com/hitzzc/go-leetcode/tree/master/binary_search_tree_iterator)
+#### [174. Dungeon Game](https://github.com/hitzzc/go-leetcode/tree/master/dungeon_game)
 
 
 
diff --git a/dungeon_game/dungeon_game.go b/dungeon_game/dungeon_game.go
@@ -0,0 +1,43 @@
+package dungeon_game
+
+func calculateMinimumHP(dungeon [][]int) int {
+	if len(dungeon) == 0 || len(dungeon[0]) == 0 {
+		return 0
+	}
+	matrix := make([][]int, len(dungeon))
+	for i := range matrix {
+		matrix[i] = make([]int, len(dungeon[0]))
+	}
+	rows := len(dungeon) - 1
+	cols := len(dungeon[0]) - 1
+	matrix[rows][cols] = dungeon[rows][cols]
+	for i := rows - 1; i >= 0; i-- {
+		matrix[i][cols] = min(dungeon[i][cols], matrix[i+1][cols]+dungeon[i][cols])
+	}
+	for j := cols - 1; j >= 0; j-- {
+		matrix[rows][j] = min(dungeon[rows][j], matrix[rows][j+1]+dungeon[rows][j])
+	}
+	for i := rows - 1; i >= 0; i-- {
+		for j := cols - 1; j >= 0; j-- {
+			matrix[i][j] = min(dungeon[i][j], dungeon[i][j]+max(matrix[i+1][j], matrix[i][j+1]))
+		}
+	}
+	if matrix[0][0] >= 0 {
+		return 1
+	}
+	return 1 - 1*matrix[0][0]
+}
+
+func max(i, j int) int {
+	if i > j {
+		return i
+	}
+	return j
+}
+
+func min(i, j int) int {
+	if i < j {
+		return i
+	}
+	return j
+}
