題目給你兩個整數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); } } PriorityQueueNode 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 切換行動編號的奇偶性 } } } } } }