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