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

2026-10-26交替方向的最小路径代价Ⅲ。用go语言给定两个整数 m、n表示网格有 m 行、n 列终点是右下角单元格 (m-1, n-1)。另有一个二维整数数组 penalty。每个单元格 (i, j) 都有一个进入费用数值为 (i1) 乘以 (j1)。起点是 (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。一、核心思路把行动编号的奇偶性变成状态的一维这道题的本质是在网格上求最小代价路径但它有一个普通最短路没有的约束能往哪个方向走取决于这是第几次行动。关键观察有三条费用只和位置的序列 哪些行动违规有关和历史无关。也就是说站在同一个格子、面对同一个奇偶性的下一步行动时未来的最优决策完全一样之前是怎么走过来的不影响。这满足最优子结构可以用最短路Dijkstra。行动编号只需要保留奇偶性。编号 1、3、5… 都是奇数允许向右/向下2、4、6… 都是偶数允许向左/向上。真正影响费用的只有下一条行动是奇数还是偶数这一个 bit。所以不需要把走了几步放进状态里否则状态数会爆炸。每次行动包括原地等待都会让编号 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)题目规定出发时先支付起点的进入费用(01)×(01) 1。此时一次行动都还没做所以下一条行动是第 1 次奇数即k 1。因此初始状态是dis[0][0][1] 1并把这个三元组(费用1, 行0, 列0, k1)放进小根堆。堆里只有一个元素天然满足堆性质不需要再调初始化。四、Dijkstra 主循环的每一轮循环里反复做四件事弹出堆顶即当前费用最小、还没确定的状态(d, i, j, k)。堆按费用d排序保证每次拿到的都是全局最小。终止判定如果这个格子就是终点(m-1, n-1)直接返回d。这里可以立刻返回是因为 Dijkstra 的性质——所有边权非负入口费和 penalty 都 ≥ 0堆顶弹出的顺序就是代价递增的顺序第一次弹出终点的那个代价无论是奇数态还是偶数态都已经是全局最小后面再弹出终点只会更大。题目也不要求到达时必须处于某个奇偶性落到终点即结束。惰性删除如果d dis[i][j][k]说明这是当初入堆后被更优路径超越的过期记录直接跳过不做扩展。扩展当前状态的两类共 5 条转移做松弛算出的新代价更小才更新dis并入堆否则丢弃。因为网格一定连通、起点到终点必然可达循环一定会命中第 2 步返回不需要处理堆空的情况。五、三类转移的具体代价公式设当前状态是(i, j, k)费用d当前格子的罚值p penalty[i][j]目标格记为(x, y)。无论哪种转移k都翻转为k^1。转移条件新增代价新状态原地等待无p只付当前格的 penalty不付入口费(i, j, k^1)合规移动方向下标奇偶性 k只付目标格入口费(x1)·(y1)(x, y, k^1)违规移动方向下标奇偶性 ! k目标格入口费(x1)·(y1)p源格 penalty(x, y, k^1)统一写法就是代码里的d (x1)(y1) (idx%2 异或 k) × p。四个方向都要先做越界检查越界的不产生转移。注意一个容易忽略的点入口费是每次进入都要付的重新走进一个以前来过的格子同样要再付一次。状态里带上奇偶性维度之后这种绕回某格但奇偶性不同的重复访问被正确区分了不会算错。六、用样例完整跑一遍m2, n2, 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, k1) }dis[0][0][1] 1。第 1 轮—— 弹出(1, (0,0), k1)未到终点p 5等待 → 代价 15 6记dis[0][0][0] 6向下到 (1,0)下标 1奇 k1合规 → 1 2 3记dis[1][0][0] 3向右到 (0,1)下标 3奇 k1合规 → 1 2 3记dis[0][1][0] 3上、左越界忽略。第 2 轮—— 弹出最小的(3, (1,0), k0)p penalty[1][0] 1等待 → 31 4记dis[1][0][1] 4向上到 (0,0)下标 0偶 k0合规 → 31 4但dis[0][0][1]已是 1不更新向右到 (1,1)下标 3奇≠ k0违规→ 3 4 1 8记dis[1][1][1] 8下、左越界。第 3 轮—— 弹出(3, (0,1), k0)p penalty[0][1] 3等待 → 33 6记dis[0][1][1] 6向下到 (1,1)下标 1奇≠ k0违规 → 3 4 3 10比已有的 8 大不更新向左到 (0,0)合规 → 31 4比 1 大不更新。第 4 轮—— 弹出(4, (1,0), k1)p 1等待 → 41 5比dis[1][0][0] 3大不更新向右到 (1,1)下标 3奇 k1合规→ 4 4 8记dis[1][1][0] 8。这一条路径就是先等待一拍把奇偶性掰成奇数再合规地向右恰好与直接违规向右同价。第 5 轮起—— 依次弹出(6,(0,0),0)、(6,(0,1),1)等它们扩展出的代价分别是 13、10 之类都压不低已有记录全部无效。最终—— 堆中最小的剩余项是代价 8 的(1,1)状态无论是 k1 还是 k0。弹出时i1m-1、j1n-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)距离数组dis2·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/heapfmtmath)// 奇数下标 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.kifim-1jn-1{returnint64(d)}ifddis[i][j][k]{continue}p:penalty[i][j]// 原地不动newDis:dpifnewDisdis[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:idir.x,jdir.yif0xxm0yyn{// 如果 k 和 idx 的奇偶性不同那么违反了奇偶性规则需要额外支付 p 的代价newDisd(x1)*(y1)(idx%2^k)*pifnewDisdis[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].dish[j].dis}func(h hp)Swap(i,jint){h[i],h[j]h[j],h[i]}func(h*hp)Push(v any){*happend(*h,v.(tuple))}func(h*hp)Pop()(v any){a:*h;*h,va[: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)]inffloat(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,kheapq.heappop(heap)ifim-1andjn-1:returndifddist[i][j][k]:continueppenalty[i][j]nkk^1# 执行一次行动后行动编号奇偶性切换# 在当前单元格等待new_disdpifnew_disdist[i][j][nk]:dist[i][j][nk]new_dis heapq.heappush(heap,(new_dis,i,j,nk))# 尝试向四个相邻方向移动foridx,(dx,dy)inenumerate(dirs):x,yidx,jdyif0xmand0yn:# 如果方向不符合当前行动编号的奇偶性要求需要额外支付 penalty[i][j]extra((idx1)^k)*p new_disd(x1)*(y1)extraifnew_disdist[x][y][nk]:dist[x][y][nk]new_dis heapq.heappush(heap,(new_dis,x,y,nk))return-1if__name____main__:m2n2penalty[[5,3],[1,4]]resultmin_cost(m,n,penalty)print(result)C完整代码如下#includebits/stdc.husingnamespacestd;structTuple{longlongdis;intx,y,k;// 小根堆按 dis 升序booloperator(constTupleo)const{returndiso.dis;}};longlongminCost(intm,intn,vectorvectorintpenalty){// idx 0: 向左idx 1: 向右idx 2: 向上idx 3: 向下// 奇数下标 1,3 对应向右或向下// 偶数下标 0,2 对应向左或向上constpairint,intdirs[4]{{0,-1},{0,1},{-1,0},{1,0}};constlonglongINFLLONG_MAX;// dis[i][j][k]到达 (i, j) 且下一次行动奇偶性为 k 的最小费用vectorvectorarraylonglong,2dis(m,vectorarraylonglong,2(n,{INF,INF}));// 起点入口代价为 (01)*(01) 1行动编号从 1 开始初始 k 1dis[0][0][1]1;// 小根堆priority_queueTuple,vectorTuple,greaterTuplepq;pq.push({1,0,0,1});while(!pq.empty()){Tuple tpq.top();pq.pop();longlongdt.dis;intit.x,jt.y,kt.k;if(im-1jn-1){returnd;}if(ddis[i][j][k]){continue;}longlongppenalty[i][j];intnkk^1;// 执行一次行动后行动编号奇偶性切换// 原地等待longlongnewDisdp;if(newDisdis[i][j][nk]){dis[i][j][nk]newDis;pq.push({newDis,i,j,nk});}// 移动一步for(intidx0;idx4;idx){intxidirs[idx].first;intyjdirs[idx].second;if(x0xmy0yn){// 如果方向奇偶性与当前行动编号奇偶性不一致违反规则需额外支付 penaltylonglongextra(longlong)((idx%2)^k)*p;newDisd(longlong)(x1)*(y1)extra;if(newDisdis[x][y][nk]){dis[x][y][nk]newDis;pq.push({newDis,x,y,nk});}}}}return-1;}intmain(){intm2,n2;vectorvectorintpenalty{{5,3},{1,4}};longlongresultminCost(m,n,penalty);coutresultendl;return0;}