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。

统一写法就是代码里的：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完整代码如下：

packagemainimport("container/heap""fmt""math")// 奇数下标 1,3 对应向右或向下// 偶数下标 0,2 对应向左或向上vardirs=[]struct{x,yint}{{0,-1},{0,1},{-1,0},{1,0}}funcminCost(m,nint,penalty[][]int)int64{dis:=make([][][2]int,m)fori:=rangedis{dis[i]=make([][2]int,n)forj:=rangedis[i]{dis[i][j]=[2]int{math.MaxInt,math.MaxInt}}}// 支付 1 的入口代价dis[0][0][1]=1h:=&hp{{1,0,0,1}}for{top:=heap.Pop(h).(tuple)d,i,j,k:=top.dis,top.x,top.y,top.kifi==m-1&&j==n-1{returnint64(d)}ifd>dis[i][j][k]{continue}p:=penalty[i][j]// 原地不动newDis:=d+pifnewDis<dis[i][j][k^1]{dis[i][j][k^1]=newDis heap.Push(h,tuple{newDis,i,j,k^1})// k^1 切换行动编号的奇偶性}// 移动一步foridx,dir:=rangedirs{x,y:=i+dir.x,j+dir.yif0<=x&&x<m&&0<=y&&y<n{// 如果 k 和 idx 的奇偶性不同，那么违反了奇偶性规则，需要额外支付 p 的代价newDis=d+(x+1)*(y+1)+(idx%2^k)*pifnewDis<dis[x][y][k^1]{dis[x][y][k^1]=newDis heap.Push(h,tuple{newDis,x,y,k^1})// k^1 切换行动编号的奇偶性}}}}}typetuplestruct{dis,x,y,kint}typehp[]tuplefunc(h hp)Len()int{returnlen(h)}func(h hp)Less(i,jint)bool{returnh[i].dis<h[j].dis}func(h hp)Swap(i,jint){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}funcmain(){m:=2n:=2penalty:=[][]int{{5,3},{1,4}}result:=minCost(m,n,penalty)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-importheapqdefmin_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_inrange(n)]for_inrange(m)]# 起点入口费用为 (0 + 1) * (0 + 1) = 1# 行动编号从 1 开始，因此初始 k = 1dist[0][0][1]=1heap=[(1,0,0,1)]# (当前费用, 行, 列, 当前行动奇偶性)whileheap:d,i,j,k=heapq.heappop(heap)ifi==m-1andj==n-1:returndifd>dist[i][j][k]:continuep=penalty[i][j]nk=k^1# 执行一次行动后，行动编号奇偶性切换# 在当前单元格等待new_dis=d+pifnew_dis<dist[i][j][nk]:dist[i][j][nk]=new_dis heapq.heappush(heap,(new_dis,i,j,nk))# 尝试向四个相邻方向移动foridx,(dx,dy)inenumerate(dirs):x,y=i+dx,j+dyif0<=x<mand0<=y<n:# 如果方向不符合当前行动编号的奇偶性要求，需要额外支付 penalty[i][j]extra=((idx&1)^k)*p new_dis=d+(x+1)*(y+1)+extraifnew_dis<dist[x][y][nk]:dist[x][y][nk]=new_dis heapq.heappush(heap,(new_dis,x,y,nk))return-1if__name__=="__main__":m=2n=2penalty=[[5,3],[1,4]]result=min_cost(m,n,penalty)print(result)

C++完整代码如下：

#include<bits/stdc++.h>usingnamespacestd;structTuple{longlongdis;intx,y,k;// 小根堆：按 dis 升序booloperator>(constTuple&o)const{returndis>o.dis;}};longlongminCost(intm,intn,vector<vector<int>>&penalty){// idx 0: 向左；idx 1: 向右；idx 2: 向上；idx 3: 向下// 奇数下标 1,3 对应向右或向下// 偶数下标 0,2 对应向左或向上constpair<int,int>dirs[4]={{0,-1},{0,1},{-1,0},{1,0}};constlonglongINF=LLONG_MAX;// dis[i][j][k]：到达 (i, j) 且下一次行动奇偶性为 k 的最小费用vector<vector<array<longlong,2>>>dis(m,vector<array<longlong,2>>(n,{INF,INF}));// 起点入口代价为 (0+1)*(0+1) = 1，行动编号从 1 开始，初始 k = 1dis[0][0][1]=1;// 小根堆priority_queue<Tuple,vector<Tuple>,greater<Tuple>>pq;pq.push({1,0,0,1});while(!pq.empty()){Tuple t=pq.top();pq.pop();longlongd=t.dis;inti=t.x,j=t.y,k=t.k;if(i==m-1&&j==n-1){returnd;}if(d>dis[i][j][k]){continue;}longlongp=penalty[i][j];intnk=k^1;// 执行一次行动后，行动编号奇偶性切换// 原地等待longlongnewDis=d+p;if(newDis<dis[i][j][nk]){dis[i][j][nk]=newDis;pq.push({newDis,i,j,nk});}// 移动一步for(intidx=0;idx<4;++idx){intx=i+dirs[idx].first;inty=j+dirs[idx].second;if(x>=0&&x<m&&y>=0&&y<n){// 如果方向奇偶性与当前行动编号奇偶性不一致，违反规则，需额外支付 penaltylonglongextra=(longlong)((idx%2)^k)*p;newDis=d+(longlong)(x+1)*(y+1)+extra;if(newDis<dis[x][y][nk]){dis[x][y][nk]=newDis;pq.push({newDis,x,y,nk});}}}}return-1;}intmain(){intm=2,n=2;vector<vector<int>>penalty={{5,3},{1,4}};longlongresult=minCost(m,n,penalty);cout<<result<<endl;return0;}