给你两个整数 m 和 n,表示一个网格的行数和列数。你的目标是到达单元格 (m - 1, n - 1)。同时给你一个二维整数数组 penalty。
进入单元格 (i, j) 的代价为 (i + 1) * (j + 1)。
你从单元格 (0, 0) 开始,最初需要支付其入口代价。进入 (0, 0) 后执行的行动从 1 开始编号。
在每次行动中,你可以移动到一个 相邻 的单元格,或者在当前单元格等待。如果满足以下条件,则移动遵循奇偶性规则:
行动的代价由以下方式决定:
penalty[i][j],其中 (i, j) 是你移动前所在的单元格。(i, j) 中等待,支付 penalty[i][j]。在每次移动或等待之后,行动编号增加 1。因此,无论是否支付了惩罚代价,所需遵循的奇偶性规则在每次行动后都会交替改变。
返回到达 (m - 1, n - 1) 所需的 最小 总代价。
示例 1:
输入: m = 2, n = 2, penalty = [[5,3],[1,4]]
输出: 8
解释:
最优路径为:
(0, 0) 开始,入口代价为 (0 + 1) * (0 + 1) = 1。(1, 0),入口代价为 (1 + 1) * (0 + 1) = 2。(1, 1),入口代价为 (1 + 1) * (1 + 1) = 4,因为违反了偶数奇偶性规则,额外代价为 penalty[1][0] = 1。因此,总代价为 1 + 2 + 4 + 1 = 8。
示例 2:
输入: m = 2, n = 2, penalty = [[0,7],[3,2]]
输出: 7
解释:
最优路径为:
(0, 0) 开始,入口代价为 (0 + 1) * (0 + 1) = 1。(0, 0) 等待,额外代价为 penalty[0][0] = 0,将奇偶性翻转为偶数。(0, 1),入口代价为 (0 + 1) * (1 + 1) = 2,因为违反了偶数奇偶性规则,额外代价为 penalty[0][0] = 0。(1, 1),入口代价为 (1 + 1) * (1 + 1) = 4。因此,总代价为 1 + 0 + 2 + 0 + 4 = 7。
示例 3:
输入: m = 2, n = 3, penalty = [[8,0,9],[7,4,1]]
输出: 12
解释:
最优路径为:
(0, 0) 开始,入口代价为 (0 + 1) * (0 + 1) = 1。(0, 1),入口代价为 (0 + 1) * (1 + 1) = 2。(0, 2),入口代价为 (0 + 1) * (2 + 1) = 3,因为违反了偶数奇偶性规则,额外代价为 penalty[0][1] = 0。(1, 2),入口代价为 (1 + 1) * (2 + 1) = 6。因此,总代价为 1 + 2 + 3 + 0 + 6 = 12。
提示:
1 <= m, n <= 1052 <= m * n <= 105penalty.length == mpenalty[i].length == n0 <= penalty[i][j] <= 105