 出发，走到右下角单元格 (m-1,n-1)。 在移动过程)
2026-07-16网格图中最小异或路径。用go语言给定一个大小为 m × n 的二维整数矩阵 grid。你需要从左上角单元格 (0,0) 出发走到右下角单元格 (m-1,n-1)。在移动过程中每一步只能向右移动或向下移动对任意一条从起点到终点的路径其代价定义为路径经过的所有格子包含起点和终点里的数值做按位异或XOR得到的结果。你的任务是在所有可行路径里找出异或结果最小的那个值并返回它。1 m grid.length 1000。1 n grid[i].length 1000。m * n 1000。0 grid[i][j] 1023。输入 grid [[1,2],[3,4]]。输出 6。解释有两条有效路径(0, 0) → (0, 1) → (1, 1)异或值为1 XOR 2 XOR 4 7(0, 0) → (1, 0) → (1, 1)异或值为1 XOR 3 XOR 4 6所有有效路径中的最小异或值为 6。题目来自力扣3882。一、分步详细执行流程步骤1遍历整个网格计算全局所有数字的按位或总和 orAll初始化orAll 0双层循环遍历矩阵每一个格子数字x执行orAll orAll | x作用所有路径异或结果一定不会超过orAll数字最大1023异或结果上限就是1023以此确定异或值维度的最大长度用来开辟访问数组。步骤2创建三维访问标记数组 vis[i][j][xorVal]数组三维含义第一维i网格行坐标第二维j网格列坐标第三维xor走到(i,j)时已经累积的异或中间值布尔值含义true代表该坐标该异或值组合已经递归处理过无需重复搜索核心剪枝手段。开辟逻辑先创建m行的二维切片每行创建n列切片每个格子开辟长度orAll 1的布尔数组覆盖全部可能出现的异或数值。步骤3初始化全局答案 ansans赋值为系统最大整数math.MaxInt作为最小值的初始无穷大占位后续路径异或结果会不断更小覆盖它。步骤4定义递归DFS函数反向回溯逻辑函数入参i,j,xori,j当前递归所在网格坐标初始调用是终点m-1,n-1xor从终点往回走到当前格子前已经累积的异或中间值初始调用传0。DFS内部完整执行分支拆解分支1提前终止剪枝条件直接返回不继续递归满足任意一条就退出当前递归ans 0已经找到异或等于0的最优解不可能存在更小值全部搜索停止i 0 或 j 0反向回溯走出网格边界非法坐标vis[i][j][xor] true当前坐标当前异或值组合之前搜过重复状态无需重复遍历。分支2标记当前状态为已访问如果没有触发提前终止立刻设置vis[i][j][xor] true记录该(i,j,xor)状态已处理防止其他路径再次进入相同状态造成重复计算。分支3把当前格子的值并入累积异或执行xor ^ grid[i][j]反向回溯时每走到一个格子就要把该格子数字参与异或运算和正向路径所有数字异或结果完全等价。原理异或满足交换律、结合律正向从起点一路异或到终点 反向从终点一路异或到起点。分支4判断是否抵达起点更新最小答案如果当前坐标i0 j0说明完整走完一条合法路径从终点反向回到起点用min(ans, xor)更新全局最小值ans当前递归结束return。分支5反向递归两个合法前序格子正向只能向右、向下走反向回溯就只能向上、向左走分别发起两层递归向上走一格调用dfs(i-1, j, xor)向左走一格调用dfs(i, j-1, xor)递归结束后当前函数出栈回溯上层。步骤5启动DFS入口从右下角终点开始反向搜索dfs(m-1, n-1, 0)初始累积异或值为0。步骤6返回最终最小异或结果所有递归全部执行完毕后全局变量ans存储所有合法路径的最小异或值函数返回ans。步骤7main函数测试流程定义测试矩阵[[1,2],[3,4]]调用minCost函数计算最小异或打印输出结果6。二、算法复杂度分析1. 时间复杂度状态总数上限总格子数S m*n ≤ 1000异或取值上限V orAll 1 ≤ 1024所有不重复状态总数 S × V ≤ 1000 × 1024 1,024,000。每个状态只会被访问一次三维vis数组标记访问后不再重复处理每个状态内部仅两次递归调用、常数次位运算、判断操作单次状态处理时间为O(1)。总时间复杂度O(m × n × V) O(1000 × 1024) O(1e6)可简写为 O(mn·C)C为数字值域上限1024。2. 额外空间复杂度不含输入grid存储仅算法额外开辟空间三维vis数组空间m × n × (orAll1)最大占用1000 × 1024布尔空间DFS递归栈深度最长路径格子数为mn-1一路向下再一路向右m、n最大1000但mn≤1000栈深最多1000级临时变量、循环变量均为常数空间可忽略。总额外空间复杂度O(m × n × C)C1024由三维访问数组主导递归栈空间远小于数组空间可合并计入该项。Go完整代码如下packagemainimport(fmtmath)funcminCost(grid[][]int)int{m,n:len(grid),len(grid[0])// 异或和不会超过所有元素的 ORorAll:0for_,row:rangegrid{for_,x:rangerow{orAll|x}}vis:make([][][]bool,m)fori:rangevis{vis[i]make([][]bool,n)forj:rangevis[i]{vis[i][j]make([]bool,orAll1)}}ans:math.MaxIntvardfsfunc(int,int,int)dfsfunc(i,j,xorint){// 最优性剪枝如果答案已经最小等于 0那么不再搜索ifans0||i0||j0||vis[i][j][xor]{return}vis[i][j][xor]truexor^grid[i][j]ifi0j0{ansmin(ans,xor)return}dfs(i-1,j,xor)dfs(i,j-1,xor)}dfs(m-1,n-1,0)returnans}funcmain(){grid:[][]int{{1,2},{3,4}}result:minCost(grid)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importsysdefminCost(grid):m,nlen(grid),len(grid[0])# 计算所有元素的按位或作为异或和的上界or_all0forrowingrid:forxinrow:or_all|x# visited[i][j][xor] 表示状态 (i, j, xor) 是否已被访问visited[[[False]*(or_all1)for_inrange(n)]for_inrange(m)]ansfloat(inf)sys.setrecursionlimit(1000000)# 防止递归深度过大defdfs(i,j,xor):nonlocalans# 最优性剪枝答案已为 0 无需继续ifans0ori0orj0orvisited[i][j][xor]:returnvisited[i][j][xor]Truexor^grid[i][j]# 累积当前格子的值ifi0andj0:# 到达左上角更新答案ansmin(ans,xor)returndfs(i-1,j,xor)# 向上移动dfs(i,j-1,xor)# 向左移动dfs(m-1,n-1,0)# 从右下角开始returnansif__name____main__:grid[[1,2],[3,4]]resultminCost(grid)print(result)C完整代码如下#includeiostream#includevector#includeclimits#includefunctionalusingnamespacestd;intminCost(vectorvectorintgrid){intmgrid.size();intngrid[0].size();// 计算所有元素的按位或作为异或和的上界intorAll0;for(constautorow:grid){for(intx:row){orAll|x;}}// visited[i][j][xor] 表示状态是否已经访问过vectorvectorvectorboolvis(m,vectorvectorbool(n,vectorbool(orAll1,false)));intansINT_MAX;// 递归 DFS使用 std::function 支持 lambda 自引用functionvoid(int,int,int)dfs[](inti,intj,intxorVal){// 最优性剪枝 边界检查 状态判重短路保证安全if(ans0||i0||j0||vis[i][j][xorVal]){return;}vis[i][j][xorVal]true;xorVal^grid[i][j];// 累加当前格子的值if(i0j0){// 到达起点更新答案ansmin(ans,xorVal);return;}dfs(i-1,j,xorVal);// 向上走dfs(i,j-1,xorVal);// 向左走};dfs(m-1,n-1,0);// 从右下角开始搜索returnans;}intmain(){vectorvectorintgrid{{1,2},{3,4}};coutminCost(grid)endl;return0;}
2026-07-16网格图中最小异或路径。用go语言给定一个大小为 m × n 的二维整数矩阵 grid。你需要从左上角单元格 (0,0) 出发走到右下角单元格 (m-1,n-1)。在移动过程中每一步只能向右移动或向下移动对任意一条从起点到终点的路径其代价定义为路径经过的所有格子包含起点和终点里的数值做按位异或XOR得到的结果。你的任务是在所有可行路径里找出异或结果最小的那个值并返回它。1 m grid.length 1000。1 n grid[i].length 1000。m * n 1000。0 grid[i][j] 1023。输入 grid [[1,2],[3,4]]。输出 6。解释有两条有效路径(0, 0) → (0, 1) → (1, 1)异或值为1 XOR 2 XOR 4 7(0, 0) → (1, 0) → (1, 1)异或值为1 XOR 3 XOR 4 6所有有效路径中的最小异或值为 6。题目来自力扣3882。一、分步详细执行流程步骤1遍历整个网格计算全局所有数字的按位或总和 orAll初始化orAll 0双层循环遍历矩阵每一个格子数字x执行orAll orAll | x作用所有路径异或结果一定不会超过orAll数字最大1023异或结果上限就是1023以此确定异或值维度的最大长度用来开辟访问数组。步骤2创建三维访问标记数组 vis[i][j][xorVal]数组三维含义第一维i网格行坐标第二维j网格列坐标第三维xor走到(i,j)时已经累积的异或中间值布尔值含义true代表该坐标该异或值组合已经递归处理过无需重复搜索核心剪枝手段。开辟逻辑先创建m行的二维切片每行创建n列切片每个格子开辟长度orAll 1的布尔数组覆盖全部可能出现的异或数值。步骤3初始化全局答案 ansans赋值为系统最大整数math.MaxInt作为最小值的初始无穷大占位后续路径异或结果会不断更小覆盖它。步骤4定义递归DFS函数反向回溯逻辑函数入参i,j,xori,j当前递归所在网格坐标初始调用是终点m-1,n-1xor从终点往回走到当前格子前已经累积的异或中间值初始调用传0。DFS内部完整执行分支拆解分支1提前终止剪枝条件直接返回不继续递归满足任意一条就退出当前递归ans 0已经找到异或等于0的最优解不可能存在更小值全部搜索停止i 0 或 j 0反向回溯走出网格边界非法坐标vis[i][j][xor] true当前坐标当前异或值组合之前搜过重复状态无需重复遍历。分支2标记当前状态为已访问如果没有触发提前终止立刻设置vis[i][j][xor] true记录该(i,j,xor)状态已处理防止其他路径再次进入相同状态造成重复计算。分支3把当前格子的值并入累积异或执行xor ^ grid[i][j]反向回溯时每走到一个格子就要把该格子数字参与异或运算和正向路径所有数字异或结果完全等价。原理异或满足交换律、结合律正向从起点一路异或到终点 反向从终点一路异或到起点。分支4判断是否抵达起点更新最小答案如果当前坐标i0 j0说明完整走完一条合法路径从终点反向回到起点用min(ans, xor)更新全局最小值ans当前递归结束return。分支5反向递归两个合法前序格子正向只能向右、向下走反向回溯就只能向上、向左走分别发起两层递归向上走一格调用dfs(i-1, j, xor)向左走一格调用dfs(i, j-1, xor)递归结束后当前函数出栈回溯上层。步骤5启动DFS入口从右下角终点开始反向搜索dfs(m-1, n-1, 0)初始累积异或值为0。步骤6返回最终最小异或结果所有递归全部执行完毕后全局变量ans存储所有合法路径的最小异或值函数返回ans。步骤7main函数测试流程定义测试矩阵[[1,2],[3,4]]调用minCost函数计算最小异或打印输出结果6。二、算法复杂度分析1. 时间复杂度状态总数上限总格子数S m*n ≤ 1000异或取值上限V orAll 1 ≤ 1024所有不重复状态总数 S × V ≤ 1000 × 1024 1,024,000。每个状态只会被访问一次三维vis数组标记访问后不再重复处理每个状态内部仅两次递归调用、常数次位运算、判断操作单次状态处理时间为O(1)。总时间复杂度O(m × n × V) O(1000 × 1024) O(1e6)可简写为 O(mn·C)C为数字值域上限1024。2. 额外空间复杂度不含输入grid存储仅算法额外开辟空间三维vis数组空间m × n × (orAll1)最大占用1000 × 1024布尔空间DFS递归栈深度最长路径格子数为mn-1一路向下再一路向右m、n最大1000但mn≤1000栈深最多1000级临时变量、循环变量均为常数空间可忽略。总额外空间复杂度O(m × n × C)C1024由三维访问数组主导递归栈空间远小于数组空间可合并计入该项。Go完整代码如下packagemainimport(fmtmath)funcminCost(grid[][]int)int{m,n:len(grid),len(grid[0])// 异或和不会超过所有元素的 ORorAll:0for_,row:rangegrid{for_,x:rangerow{orAll|x}}vis:make([][][]bool,m)fori:rangevis{vis[i]make([][]bool,n)forj:rangevis[i]{vis[i][j]make([]bool,orAll1)}}ans:math.MaxIntvardfsfunc(int,int,int)dfsfunc(i,j,xorint){// 最优性剪枝如果答案已经最小等于 0那么不再搜索ifans0||i0||j0||vis[i][j][xor]{return}vis[i][j][xor]truexor^grid[i][j]ifi0j0{ansmin(ans,xor)return}dfs(i-1,j,xor)dfs(i,j-1,xor)}dfs(m-1,n-1,0)returnans}funcmain(){grid:[][]int{{1,2},{3,4}}result:minCost(grid)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importsysdefminCost(grid):m,nlen(grid),len(grid[0])# 计算所有元素的按位或作为异或和的上界or_all0forrowingrid:forxinrow:or_all|x# visited[i][j][xor] 表示状态 (i, j, xor) 是否已被访问visited[[[False]*(or_all1)for_inrange(n)]for_inrange(m)]ansfloat(inf)sys.setrecursionlimit(1000000)# 防止递归深度过大defdfs(i,j,xor):nonlocalans# 最优性剪枝答案已为 0 无需继续ifans0ori0orj0orvisited[i][j][xor]:returnvisited[i][j][xor]Truexor^grid[i][j]# 累积当前格子的值ifi0andj0:# 到达左上角更新答案ansmin(ans,xor)returndfs(i-1,j,xor)# 向上移动dfs(i,j-1,xor)# 向左移动dfs(m-1,n-1,0)# 从右下角开始returnansif__name____main__:grid[[1,2],[3,4]]resultminCost(grid)print(result)C完整代码如下#includeiostream#includevector#includeclimits#includefunctionalusingnamespacestd;intminCost(vectorvectorintgrid){intmgrid.size();intngrid[0].size();// 计算所有元素的按位或作为异或和的上界intorAll0;for(constautorow:grid){for(intx:row){orAll|x;}}// visited[i][j][xor] 表示状态是否已经访问过vectorvectorvectorboolvis(m,vectorvectorbool(n,vectorbool(orAll1,false)));intansINT_MAX;// 递归 DFS使用 std::function 支持 lambda 自引用functionvoid(int,int,int)dfs[](inti,intj,intxorVal){// 最优性剪枝 边界检查 状态判重短路保证安全if(ans0||i0||j0||vis[i][j][xorVal]){return;}vis[i][j][xorVal]true;xorVal^grid[i][j];// 累加当前格子的值if(i0j0){// 到达起点更新答案ansmin(ans,xorVal);return;}dfs(i-1,j,xorVal);// 向上走dfs(i,j-1,xorVal);// 向左走};dfs(m-1,n-1,0);// 从右下角开始搜索returnans;}intmain(){vectorvectorintgrid{{1,2},{3,4}};coutminCost(grid)endl;return0;}
