題目給你兩個整數(shù)m和n表示一個網(wǎng)格的行數(shù)和列數(shù)。你的目標(biāo)是到達(dá)單元格(m - 1, n - 1)。同時給你一個二維整數(shù)數(shù)組penalty。進(jìn)入單元格(i, j)的代價為(i 1) * (j 1)。你從單元格(0, 0)開始最初需要支付其入口代價。進(jìn)入(0, 0)后執(zhí)行的行動從 1 開始編號。在每次行動中你可以移動到一個相鄰的單元格或者在當(dāng)前單元格等待。如果滿足以下條件則移動遵循奇偶性規(guī)則在奇數(shù)編號的行動中你向右或向下移動。在偶數(shù)編號的行動中你向左或向上移動。行動的代價由以下方式?jīng)Q定如果你遵循奇偶性規(guī)則移動只需支付目標(biāo)單元格的入口代價。如果你在違反奇偶性規(guī)則的方向上移動支付目標(biāo)單元格的入口代價加上penalty[i][j]其中(i, j)是你移動前所在的單元格。如果你在單元格(i, j)中等待支付penalty[i][j]。在每次移動或等待之后行動編號增加 1。因此無論是否支付了懲罰代價所需遵循的奇偶性規(guī)則在每次行動后都會交替改變。返回到達(dá)(m - 1, n - 1)所需的最小總代價。示例 1輸入m 2, n 2, penalty [[5,3],[1,4]]輸出8解釋最優(yōu)路徑為從單元格(0, 0)開始入口代價為(0 1) * (0 1) 1。行動 1向下移動到單元格(1, 0)入口代價為(1 1) * (0 1) 2。行動 2向右移動到單元格(1, 1)入口代價為(1 1) * (1 1) 4因為違反了偶數(shù)奇偶性規(guī)則額外代價為penalty[1][0] 1。因此總代價為1 2 4 1 8。題解思路Dijkstra最短路徑算法模版題需要注意的是除了優(yōu)先級隊列還需要一個最小值數(shù)組維護(hù)答案舉例比如從A出發(fā)到C有兩條路徑A-C是權(quán)值是5先A-B,全值是3然后B-C,權(quán)值是4按優(yōu)先級隊列會先走A-B再走B-C權(quán)值和是7但實際上是從A-C權(quán)值是5權(quán)值最小這就需要一個最小值數(shù)組另外需要考慮的就是最小值數(shù)組維護(hù)的維度。class Solution { // 奇數(shù)下標(biāo) 1,3 對應(yīng)向右或向下 // 偶數(shù)下標(biāo) 0,2 對應(yīng)向左或向上 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 的奇偶性不同那么違反了奇偶性規(guī)則需要額外支付 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 切換行動編號的奇偶性 } } } } } }