2026-10-26：交替方向的最小路径代价Ⅲ。用go语言，给定两个整数 m、n，表示网格有 m 行、n 列，终点是右下角单元格 (m-1, n-1)。另有一

2026-10-26：交替方向的最小路径代价Ⅲ。用go语言，给定两个整数 m、n，表示网格有 m 行、n 列，终点是右下角单元格 (m-1, n-1)。另有一个二维整数数组 penalty。

每个单元格 (i, j) 都有一个进入费用，数值为 (i+1) 乘以 (j+1)。起点是 (0, 0)，出发时先支付起点的进入费用。

从起点进入后，开始计算行动次数，第一次行动编号为 1。每次行动可以选择移动到上下左右相邻的单元格，也可以留在当前单元格不动。行动编号每执行一次就加 1，因此行动编号的奇偶性会不断交替。

移动方向受行动编号奇偶性的约束：编号为奇数时，允许向右或向下移动；编号为偶数时，允许向左或向上移动。

费用规则如下：如果移动方向符合当前行动编号要求的奇偶性，只需支付目标单元格的进入费用。如果移动方向不符合要求，则除了支付目标单元格的进入费用，还要额外支付 penalty[i][j]，其中 (i, j) 是移动前所在的单元格。若选择在当前单元格等待，则需要支付 penalty[i][j]，其中 (i, j) 就是当前所在单元格。

要求计算从 (0, 0) 到达 (m-1, n-1) 所需的最小总费用。

1 <= m, n <= 100000。

2 <= m * n <= 100000。

penalty.length == m。

penalty[i].length == n。

0 <= penalty[i][j] <= 100000。

输入： 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。

题目来自力扣4003。

一、核心思路：把”行动编号的奇偶性”变成状态的一维

这道题的本质是在网格上求最小代价路径，但它有一个普通最短路没有的约束：能往哪个方向走，取决于”这是第几次行动”。

关键观察有三条：

1.费用只和”位置的序列 + 哪些行动违规”有关，和历史无关。也就是说，站在同一个格子、面对同一个奇偶性的下一步行动时，未来的最优决策完全一样，之前是怎么走过来的不影响。这满足最优子结构，可以用最短路（Dijkstra）。

2.行动编号只需要保留奇偶性。编号 1、3、5… 都是奇数（允许向右/向下），2、4、6… 都是偶数（允许向左/向上）。真正影响费用的只有”下一条行动是奇数还是偶数”这一个 bit。所以不需要把”走了几步”放进状态里，否则状态数会爆炸。

3.每次行动（包括原地等待）都会让编号 +1，也就是奇偶性必然翻转。所以状态里那个 bit 在每次转移后都要取反。

于是原来的”m×n 个格子”被扩展成2·m·n 个状态：(格子 i,j) × (下一条行动编号的奇偶性 k)。整个问题就变成在这张扩展图上跑一次单源最短路。

顺带说明”等待”为什么必须存在：当你想连续两次往右走时，中间那一步（偶数编号）不允许向右，你必须”消耗”掉这次行动——要么原地等待，要么绕路。等待的代价是 penalty[当前格]，绕路的代价是邻格的入口费，二者孰优孰劣正需要算法去比较，所以”原地不动”是一条独立且必要的转移。

二、方向数组与奇偶性的对应关系

代码里四个方向按固定顺序排列：上、下、左、右，下标分别是 0、1、2、3。

• 下标 1（下）和 3（右）是奇数 → 对应”奇数编号允许的方向”；

• 下标 0（上）和 2（左）是偶数 → 对应”偶数编号允许的方向”。

这样一来，判断”这次移动合不合规”就退化成了一次位运算：dirs 的下标 % 2是否等于k。相等即合规，不等即违规。违规时额外付penalty[i][j]，其中(i,j)是移动前所在的格子（注意不是目标格）。

三、状态数组与初始化

• 开一个三维数组dis[i][j][k]，含义是：到达格子 (i,j)，且下一条行动的编号奇偶性为 k 时，已经付出的最小总费用。数组规模 2·m·n，初值全部设为无穷大（math.MaxInt），表示”尚未到达”。

• 起点的处理是特殊的：人一开始就在 (0,0)，题目规定出发时先支付起点的进入费用(0+1)×(0+1) = 1。此时一次行动都还没做，所以下一条行动是第 1 次（奇数），即k = 1。

• 因此初始状态是dis[0][0][1] = 1，并把这个三元组(费用=1, 行=0, 列=0, k=1)放进小根堆。堆里只有一个元素，天然满足堆性质，不需要再调初始化。

四、Dijkstra 主循环的每一轮

循环里反复做四件事：

1.弹出堆顶，即当前”费用最小、还没确定”的状态(d, i, j, k)。堆按费用d排序，保证每次拿到的都是全局最小。

2.终止判定：如果这个格子就是终点(m-1, n-1)，直接返回d。这里可以立刻返回是因为 Dijkstra 的性质——所有边权非负（入口费和 penalty 都 ≥ 0），堆顶弹出的顺序就是代价递增的顺序，第一次弹出终点的那个代价，无论是奇数态还是偶数态，都已经是全局最小，后面再弹出终点只会更大。题目也不要求”到达时必须处于某个奇偶性”，落到终点即结束。

3.惰性删除：如果d > dis[i][j][k]，说明这是当初入堆后被更优路径超越的”过期记录”，直接跳过，不做扩展。

4.扩展当前状态的两类（共 5 条）转移，做松弛：算出的新代价更小才更新dis并入堆，否则丢弃。

因为网格一定连通、起点到终点必然可达，循环一定会命中第 2 步返回，不需要处理”堆空”的情况。

五、三类转移的具体代价公式

设当前状态是(i, j, k)，费用d，当前格子的罚值p = penalty[i][j]，目标格记为(x, y)。无论哪种转移，k都翻转为k^1。

转移

条件

新增代价

新状态

原地等待

p

（只付当前格的 penalty，不付入口费）

(i, j, k^1)合规移动

方向下标奇偶性 == k

只付目标格入口费(x+1)·(y+1)

(x, y, k^1)违规移动

方向下标奇偶性 != k

目标格入口费(x+1)·(y+1)+p（源格 penalty）

(x, y, k^1)

统一写法就是代码里的：d + (x+1)(y+1) + (idx%2 异或 k) × p。四个方向都要先做越界检查，越界的不产生转移。

注意一个容易忽略的点：入口费是”每次进入”都要付的，重新走进一个以前来过的格子同样要再付一次。状态里带上奇偶性维度之后，这种”绕回某格但奇偶性不同”的重复访问被正确区分了，不会算错。

六、用样例完整跑一遍（m=2, n=2, penalty = [[5,3],[1,4]]）

各格入口费：(0,0)=1，(0,1)=2，(1,0)=2，(1,1)=4。各格 penalty：(0,0)=5，(0,1)=3，(1,0)=1，(1,1)=4。

初始：堆 = { (1, 0,0, k=1) }，dis[0][0][1] = 1。

第 1 轮—— 弹出(1, (0,0), k=1)，未到终点，p = 5：

• 等待 → 代价 1+5 = 6，记dis[0][0][0] = 6；

• 向下到 (1,0)：下标 1（奇）== k=1，合规 → 1 + 2 = 3，记dis[1][0][0] = 3；

• 向右到 (0,1)：下标 3（奇）== k=1，合规 → 1 + 2 = 3，记dis[0][1][0] = 3；

• 上、左越界，忽略。

第 2 轮—— 弹出最小的(3, (1,0), k=0)，p = penalty[1][0] = 1：

• 等待 → 3+1 = 4，记dis[1][0][1] = 4；

• 向上到 (0,0)：下标 0（偶）== k=0，合规 → 3+1 = 4，但dis[0][0][1]已是 1，不更新；

• 向右到 (1,1)：下标 3（奇）≠ k=0，违规→ 3 + 4 + 1 = 8，记dis[1][1][1] = 8；

• 下、左越界。

第 3 轮—— 弹出(3, (0,1), k=0)，p = penalty[0][1] = 3：

• 等待 → 3+3 = 6，记dis[0][1][1] = 6；

• 向下到 (1,1)：下标 1（奇）≠ k=0，违规 → 3 + 4 + 3 = 10，比已有的 8 大，不更新；

• 向左到 (0,0)：合规 → 3+1 = 4，比 1 大，不更新。

第 4 轮—— 弹出(4, (1,0), k=1)，p = 1：

• 等待 → 4+1 = 5，比dis[1][0][0] = 3大，不更新；

• 向右到 (1,1)：下标 3（奇）== k=1，合规→ 4 + 4 = 8，记dis[1][1][0] = 8。（这一条路径就是”先等待一拍把奇偶性掰成奇数，再合规地向右”，恰好与”直接违规向右”同价。）

第 5 轮起—— 依次弹出(6,(0,0),0)、(6,(0,1),1)等，它们扩展出的代价分别是 13、10 之类，都压不低已有记录，全部无效。

最终—— 堆中最小的剩余项是代价 8 的(1,1)状态（无论是 k=1 还是 k=0）。弹出时i=1=m-1、j=1=n-1，命中终点，返回8，与题目给出的解释完全一致（1 + 2 + 4 + 1）。

七、两个工程细节

•为什么返回值是 int64：所有边权非负，最优路径在状态图上不会绕环（绕环只会更贵），因此最多走 2·m·n − 1 步；每步最多付”入口费 ≤ m·n”加”penalty ≤ 10⁵”，量级可达 10¹⁰，超过 32 位整数范围，所以对外转成了int64（内部dis用int，在 64 位平台上本身就是 64 位，安全）。

•m、n 各自可达 10⁵，但 m·n ≤ 10⁵：所以按 m 行、每行 n 列来开二维数组是安全的，总元素数受m·n约束，不会退化成 10¹⁰ 的分配。

八、复杂度

设S = m·n（题目约束下 S ≤ 10⁵）。

状态数：V = 2·m·n = 2S（每个格子 × 两种奇偶性）。
边数：每个状态最多 1 条”等待”边 + 4 条”移动”边，所以E ≤ 5·V = 10·m·n。

时间复杂度：O(m·n · log(m·n))
每个状态被弹出并处理一次（过期记录直接跳过，代价可忽略），每次弹出与每次成功松弛各伴随一次堆操作 O(log V)；成功松弛的总次数不超过边数 E。总计 O((V + E)·log V) = O(m·n·log(m·n))。相对于只能 O(1) 转移的普通网格 DP，这里多出来的 log 因子来自”带权 + 可回头走”必须用堆。

额外空间复杂度：O(m·n)

• 距离数组dis：2·m·n 个整数，即 O(m·n)；

• 小根堆：条目数上界等于成功松弛次数，不超过 E = O(m·n)，每个条目是 4 个整数，仍是 O(m·n)；

• 除输入penalty外没有其他随规模增长的结构。

代入上限 S = 10⁵：约 2×10⁵ 个状态、最多约 10⁶ 次入堆，距离数组约 1.6 MB，整体跑得非常轻松。

Go完整代码如下：

package main

 import (
    "container/heap"
    "fmt"
    "math"
)

 // 奇数下标 1,3 对应向右或向下
// 偶数下标 0,2 对应向左或向上
var dirs = []struct{ x, y int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}

 func minCost(m, n int, penalty [][]int)int64 {
    dis := make([][][2]int, m)
    for i := range dis {
        dis[i] = make([][2]int, n)
        for j := range dis[i] {
            dis[i][j] = [2]int{math.MaxInt, math.MaxInt}
        }
    }

     // 支付 1 的入口代价
    dis[0][0][1] = 1
    h := &hp{{1, 0, 0, 1}}

     for {
        top := heap.Pop(h).(tuple)
        d, i, j, k := top.dis, top.x, top.y, top.k
        if i == m-1 && j == n-1 {
            returnint64(d)
        }
        if d > dis[i][j][k] {
            continue
        }
        p := penalty[i][j]

         // 原地不动
        newDis := d + p
        if newDis < dis[i][j][k^1] {
            dis[i][j][k^1] = newDis
            heap.Push(h, tuple{newDis, i, j, k ^ 1}) // k^1 切换行动编号的奇偶性
        }

         // 移动一步
        for idx, dir := range dirs {
            x, y := i+dir.x, j+dir.y
            if0 <= 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
                    heap.Push(h, tuple{newDis, x, y, k ^ 1}) // k^1 切换行动编号的奇偶性
                }
            }
        }
    }
}

 type tuple struct{ dis, x, y, k int }
type hp []tuple

 func (h hp) Len() int           { returnlen(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() (v any)      { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }

 func main() {
    m := 2
    n := 2
    penalty := [][]int{{5, 3}, {1, 4}}
    result := minCost(m, n, penalty)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 import heapq

 def min_cost(m: int, n: int, penalty: list[list[int]]) -> int:
    # 索引 0：向左；索引 1：向右；索引 2：向上；索引 3：向下
    dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]

     inf = float("inf")

     # dist[i][j][k] 表示到达 (i, j) 且下一次行动奇偶性为 k 时的最小费用
    # k = 1 表示奇数编号行动，k = 0 表示偶数编号行动
    dist = [[[inf, inf] for _ in range(n)] for _ in range(m)]

     # 起点入口费用为 (0 + 1) * (0 + 1) = 1
    # 行动编号从 1 开始，因此初始 k = 1
    dist[0][0][1] = 1

     heap = [(1, 0, 0, 1)]  # (当前费用, 行, 列, 当前行动奇偶性)

     while heap:
        d, i, j, k = heapq.heappop(heap)

         if i == m - 1 and j == n - 1:
            return d

         if d > dist[i][j][k]:
            continue

         p = penalty[i][j]
        nk = k ^ 1  # 执行一次行动后，行动编号奇偶性切换

         # 在当前单元格等待
        new_dis = d + p
        if new_dis < dist[i][j][nk]:
            dist[i][j][nk] = new_dis
            heapq.heappush(heap, (new_dis, i, j, nk))

         # 尝试向四个相邻方向移动
        for idx, (dx, dy) in enumerate(dirs):
            x, y = i + dx, j + dy

             if0 <= x < m and 0 <= y < n:
                # 如果方向不符合当前行动编号的奇偶性要求，需要额外支付 penalty[i][j]
                extra = ((idx & 1) ^ k) * p
                new_dis = d + (x + 1) * (y + 1) + extra

                 if new_dis < dist[x][y][nk]:
                    dist[x][y][nk] = new_dis
                    heapq.heappush(heap, (new_dis, x, y, nk))

     return-1

 if __name__ == "__main__":
    m = 2
    n = 2
    penalty = [[5, 3], [1, 4]]
    result = min_cost(m, n, penalty)
    print(result)

C++完整代码如下：

  

using namespace std;

 struct Tuple {
    long long dis;
    int x, y, k;
    // 小根堆：按 dis 升序
    bool operator>(const Tuple& o) const { return dis > o.dis; }
};

 long long minCost(int m, int n, vector 
 
 int 
 >>& penalty) { 
 
 
      
 // idx 0: 向左；idx 1: 向右；idx 2: 向上；idx 3: 向下 
 
 
      
 // 奇数下标 1,3 对应向右或向下 
 
 
      
 // 偶数下标 0,2 对应向左或向上 
 
 
      
 const 
  pair< 
 int 
 ,  
 int 
 > dirs[ 
 4 
 ] = {{ 
 0 
 ,  
 -1 
 }, { 
 0 
 ,  
 1 
 }, { 
 -1 
 ,  
 0 
 }, { 
 1 
 ,  
 0 
 }}; 
 
 
      
 const 
  long long INF = LLONG_MAX; 
 
 
 
 
      
 // dis[i][j][k]：到达 (i, j) 且下一次行动奇偶性为 k 的最小费用 
 
 
     vector 
 
 2 
 >>> dis( 
 
 
         m, vector 
 
 2 
 >>(n, {INF, INF})); 
 
 
 
 
      
 // 起点入口代价为 (0+1)*(0+1) = 1，行动编号从 1 开始，初始 k = 1 
 
 
     dis[ 
 0 
 ][ 
 0 
 ][ 
 1 
 ] =  
 1 
 ; 
 
 
 
 
      
 // 小根堆 
 
 
     priority_queue 
 
 , greater 
 
 > pq; 
 
 
 
 
     pq.push({ 
 1 
 ,  
 0 
 ,  
 0 
 ,  
 1 
 }); 
 
 
 
 
     while (!pq.empty()) { 
 
 
         Tuple t = pq.top(); 
 
 
         pq.pop(); 
 
 
         long long d = t.dis; 
 
 
          
 int 
  i = t.x, j = t.y, k = t.k; 
 
 
 
 
          
 if 
  (i == m -  
 1 
  && j == n -  
 1 
 ) { 
 
 
              
 return 
  d; 
 
 
         } 
 
 
          
 if 
  (d > dis[i][j][k]) { 
 
 
              
 continue 
 ; 
 
 
         } 
 
 
 
 
         long long p = penalty[i][j]; 
 
 
          
 int 
  nk = k ^  
 1 
 ;   
 // 执行一次行动后，行动编号奇偶性切换 
 
 
 
 
          
 // 原地等待 
 
 
         long long newDis = d + p; 
 
 
          
 if 
  (newDis < dis[i][j][nk]) { 
 
 
             dis[i][j][nk] = newDis; 
 
 
             pq.push({newDis, i, j, nk}); 
 
 
         } 
 
 
 
 
          
 // 移动一步 
 
 
          
 for 
  ( 
 int 
  idx =  
 0 
 ; idx <  
 4 
 ; ++idx) { 
 
 
              
 int 
  x = i + dirs[idx].first; 
 
 
              
 int 
  y = j + dirs[idx].second; 
 
 
              
 if 
  (x >=  
 0 
  && x < m && y >=  
 0 
  && y < n) { 
 
 
                  
 // 如果方向奇偶性与当前行动编号奇偶性不一致，违反规则，需额外支付 penalty 
 
 
                 long long extra = (long long)((idx %  
 2 
 ) ^ k) * p; 
 
 
                 newDis = d + (long long)(x +  
 1 
 ) * (y +  
 1 
 ) + extra; 
 
 
                  
 if 
  (newDis < dis[x][y][nk]) { 
 
 
                     dis[x][y][nk] = newDis; 
 
 
                     pq.push({newDis, x, y, nk}); 
 
 
                 } 
 
 
             } 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
 -1 
 ; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
      
 int 
  m =  
 2 
 , n =  
 2 
 ; 
 
 
     vector 
 
 int 
 >> penalty = {{ 
 5 
 ,  
 3 
 }, { 
 1 
 ,  
 4 
 }}; 
 
 
     long long result = minCost(m, n, penalty); 
 
 
     cout << result << endl; 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。