题目

给你两个整数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：向下移动到单元格(1, 0)，入口代价为(1 + 1) * (0 + 1) = 2。
• 行动 2：向右移动到单元格(1, 1)，入口代价为(1 + 1) * (1 + 1) = 4，因为违反了偶数奇偶性规则，额外代价为penalty[1][0] = 1。

因此，总代价为1 + 2 + 4 + 1 = 8。

题解

思路：Dijkstra最短路径算法模版题，需要注意的是除了优先级队列，还需要一个最小值数组维护答案，举例：比如从A出发到C，有两条路径，A->C是权值是5，先A->B,全值是3，然后B->C,权值是4，按优先级队列，会先走A->B，再走B->C，权值和是7，但实际上是从A->C权值是5，权值最小，这就需要一个最小值数组，另外需要考虑的就是最小值数组维护的维度。

class Solution { // 奇数下标 1,3 对应向右或向下 // 偶数下标 0,2 对应向左或向上 private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下 private record Node(long d, int i, int j, int k) { } public long minCost(int m, int n, int[][] penalty) { long[][][] dis = new long[m][n][2]; for (long[][] mat : dis) { for (long[] row : mat) { Arrays.fill(row, Long.MAX_VALUE); } } PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> Long.compare(a.d, b.d)); // 支付 1 的入口代价 dis[0][0][1] = 1; pq.offer(new Node(1, 0, 0, 1)); while (true) { Node top = pq.poll(); long d = top.d; int i = top.i; int j = top.j; int k = top.k; if (i == m - 1 && j == n - 1) { return d; } if (d > dis[i][j][k]) { continue; } int p = penalty[i][j]; // 原地不动 long newDis = d + p; if (newDis < dis[i][j][k ^ 1]) { dis[i][j][k ^ 1] = newDis; pq.offer(new Node(newDis, i, j, k ^ 1)); // k^1 切换行动编号的奇偶性 } // 移动一步 for (int idx = 0; idx < 4; idx++) { int x = i + DIRS[idx][0]; int y = j + DIRS[idx][1]; if (0 <= x && x < m && 0 <= y && y < n) { // 如果 k 和 idx 的奇偶性不同，那么违反了奇偶性规则，需要额外支付 p 的代价 newDis = d + (x + 1) * (y + 1) + (idx % 2 ^ k) * p; if (newDis < dis[x][y][k ^ 1]) { dis[x][y][k ^ 1] = newDis; pq.offer(new Node(newDis, x, y, k ^ 1)); // k^1 切换行动编号的奇偶性 } } } } } }