题解 | 龙与地下城游戏问题

package main

import (
	"fmt"
)

func main() {
	n, m := 0, 0
	for {
		num, _ := fmt.Scan(&n, &m)
		if num == 0 {
			break
		} else {
			arr := make([][]int, n)
			for i := 0; i < n; i++ {
				arr[i] = make([]int, m)
				for j := 0; j < m; j++ {
					fmt.Scan(&arr[i][j])
				}
			}
			fmt.Println(process2(arr, n, m))
		}
	}
}

func process2(arr [][]int, n, m int) int {
	dp := make([][]int, n)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, m)
	}

	for i := n - 1; i >= 0; i-- {
		for j := m - 1; j >= 0; j-- {
			if i == n-1 && j == m-1 {
			    // 右下脚位置处，dp[i][j] + arr[i][j] >= 1
				dp[i][j] = 1 - arr[i][j]
			} else if i == n-1 {
			    // 最后一行位置处，
			    // 血量需要满足大于1，大于需要的血量dp[i][j+1]
				minn := max(1, dp[i][j+1])
				dp[i][j] = minn - arr[i][j]
			} else if j == m-1 {
			    // 最后一列位置处，
			    // 血量需要满足大于1，大于需要的血量dp[i+1][j]
				minn := max(1, dp[i+1][j])
				dp[i][j] = minn - arr[i][j]
			} else {
			    // 其他位置处，
			    // 血量需要满足大于1，大于最小值（dp[i+1][j]，dp[i][j+1]） 
				minn := max(1, min(dp[i][j+1], dp[i+1][j]))
				dp[i][j] = minn - arr[i][j]
			}
			// 每个[i,j]位置处均不能小于1
			if dp[i][j] < 1 {
				dp[i][j] = 1
			}
		}
	}

	return dp[0][0]
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}