174. Dungeon Game #

Problem #

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.

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.

Problem Summary #

Some demons captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon is a two-dimensional grid composed of M x N rooms. Our valiant knight (K) is initially placed in the top-left room, and he must pass through the dungeon and fight the demons to rescue the princess.

The knight’s initial health points are represented by a positive integer. If his health points drop to 0 or below at any moment, he dies immediately.

Some rooms are guarded by demons, so the knight will lose health points upon entering these rooms (if the value in the room is a negative integer, it means the knight will lose health points); other rooms are either empty (the value in the room is 0) or contain magic orbs that increase the knight’s health points (if the value in the room is a positive integer, it means the knight will gain health points).

In order to reach the princess as quickly as possible, the knight decides to move only one step rightward or downward each time. Write a function to calculate the minimum initial health points required to ensure that the knight can rescue the princess.

Note:

• The knight’s health points have no upper bound.
• Any room may threaten the knight’s health points or may increase the knight’s health points, including the top-left room the knight enters and the bottom-right room where the princess is imprisoned.

Solution Ideas #

• On a two-dimensional map, each cell gives the amount of health lost: negative numbers represent losing health, and positive numbers represent gaining health. The top-left first cell is the start, and the bottom-right last cell is the destination. Ask for the minimum initial health the knight needs to complete the maze and successfully rescue the princess at the destination. Note that both the start and the destination affect health. At every cell, the knight’s health must not be less than 1; once it is less than 1, the knight dies.

• The first solution that comes to mind for this problem is dynamic programming. Work backward from the destination to the start. dp[i][j] represents the minimum health value the knight needs before entering the cell with coordinates (i,j). Then dp[m-1][n-1] should satisfy two conditions at the same time: dp[m-1][n-1] + dungeon[m-1][n-1] ≥ 1 and dp[m-1][n-1] ≥ 1. Since the directions of these two inequalities are the same, after taking their intersection, the decisive value is the rightmost number on the number line, namely max(1-dungeon[m-1][n-1] , 1). After calculating dp[m-1][n-1], we can then derive the values of the row dp[m-1][i] and the column dp[i][n-1]. This is because the knight can only move right and down. When deriving backward, he can only move up and left. At this point, the initial conditions for DP are ready. So what is the state transition equation? Analyze the general case: the value dp[i][j] should be related to both dp[i+1][j] and dp[i][j+1]. That is, after dp[i][j] accounts for the health loss of its own cell, it must at least satisfy the minimum health requirements of the cell in the next row and the cell in the right column. Also, its own health should be ≥1. In other words, the following two sets of inequalities must be satisfied.

  \[ \begin{matrix} \left\{ \begin{array}{lr} dp[i][j] + dungeon[i][j] \geqslant dp[i+1][j] \\ dp[i][j] \geqslant 1 \end{array} \right. \end{matrix} \]

  \[ \begin{matrix} \left\{ \begin{array}{lr} dp[i][j] + dungeon[i][j] \geqslant dp[i][j+1] \\ dp[i][j] \geqslant 1 \end{array} \right. \end{matrix} \]
  In the inequalities above, the first set of inequalities satisfies the minimum health requirement of the cell in the next row, and the second set of inequalities satisfies the minimum health requirement of the cell in the right column. Simplifying the first expression gives dp[i][j] = max(1, dp[i+1][j]-dungeon[i][j]), and simplifying the second expression gives dp[i][j] = max(1, dp[i][j+1]-dungeon[i][j]). After obtaining the minimum health values for these two ways to move, take the smaller of these two values; this is the minimum health required for the current cell. Therefore, the state transition equation is dp[i][j] = min(max(1, dp[i][j+1]-dungeon[i][j]), max(1, dp[i+1][j]-dungeon[i][j])). After DP is complete, dp[0][0] records the knight’s minimum initial health value. The time complexity is O(m*n), and the space complexity is O(m*n).

• This problem can also be solved using binary search. The knight’s health value range must be within the interval [1，+∞). So binary search this interval: for each middle value, use dp on the map to determine whether the destination can be reached. If it can, shrink the search space to [1，mid]; otherwise, the search space is [mid + 1，+∞). The time complexity is O(m*n* log math.MaxInt64), and the space complexity is O(m*n).

Code #

package leetcode

import "math"

// Solution 1 Dynamic programming
func calculateMinimumHP(dungeon [][]int) int {
	if len(dungeon) == 0 {
		return 0
	}
	m, n := len(dungeon), len(dungeon[0])
	dp := make([][]int, m)
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
	}
	dp[m-1][n-1] = max(1-dungeon[m-1][n-1], 1)
	for i := n - 2; i >= 0; i-- {
		dp[m-1][i] = max(1, dp[m-1][i+1]-dungeon[m-1][i])
	}
	for i := m - 2; i >= 0; i-- {
		dp[i][n-1] = max(1, dp[i+1][n-1]-dungeon[i][n-1])
	}
	for i := m - 2; i >= 0; i-- {
		for j := n - 2; j >= 0; j-- {
			dp[i][j] = min(max(1, dp[i][j+1]-dungeon[i][j]), max(1, dp[i+1][j]-dungeon[i][j]))
		}
	}
	return dp[0][0]
}

// Solution 2 Binary search
func calculateMinimumHP1(dungeon [][]int) int {
	low, high := 1, math.MaxInt64
	for low < high {
		mid := low + (high-low)>>1
		if canCross(dungeon, mid) {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

func canCross(dungeon [][]int, start int) bool {
	m, n := len(dungeon), len(dungeon[0])
	dp := make([][]int, m)
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
	}
	for i := 0; i < len(dp); i++ {
		for j := 0; j < len(dp[i]); j++ {
			if i == 0 && j == 0 {
				dp[i][j] = start + dungeon[0][0]
			} else {
				a, b := math.MinInt64, math.MinInt64
				if i > 0 && dp[i-1][j] > 0 {
					a = dp[i-1][j] + dungeon[i][j]
				}
				if j > 0 && dp[i][j-1] > 0 {
					b = dp[i][j-1] + dungeon[i][j]
				}
				dp[i][j] = max(a, b)
			}
		}
	}
	return dp[m-1][n-1] > 0
}