2026-07-16：网格图中最小异或路径。用go语言，给定一个大小为 m × n 的二维整数矩阵 grid。你需要从左上角单元格 (0,0) 出发，走到右下

网易专栏3周前发布 nxnqh

28 0 0

发布时间：2026-07-16 02:05:02

#开发技术 | #LeetCode

来源：网易专栏作者：moonfdd
🔗 查看原文

🤖 AI总结

主题

使用DFS+三维访问数组解决网格最小异或路径问题

摘要

本文详细解析LeetCode 3882题，通过反向DFS和三维访问数组剪枝，实现网格最小异或路径的高效求解，并附多语言代码。

关键信息

1 题目为LeetCode 3882，求网格从左上到右下的最小异或路径值
2 采用反向DFS并利用三维vis数组剪枝，复杂度O(mn*C)
3 提供Go、Python、C++三种语言实现

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

1. 初始化orAll = 0；

2. 双层循环遍历矩阵每一个格子数字x；

3. 执行orAll = orAll | x；

4. 作用：所有路径异或结果一定不会超过orAll（数字最大1023，异或结果上限就是1023），以此确定异或值维度的最大长度，用来开辟访问数组。

步骤2：创建三维访问标记数组 vis[i][j][xorVal]

数组三维含义：

• 第一维i：网格行坐标；

• 第二维j：网格列坐标；

• 第三维xor：走到(i,j)时已经累积的异或中间值；
布尔值含义：true代表该坐标+该异或值组合已经递归处理过，无需重复搜索，核心剪枝手段。
开辟逻辑：

1. 先创建m行的二维切片；

2. 每行创建n列切片；

3. 每个格子开辟长度orAll + 1的布尔数组，覆盖全部可能出现的异或数值。

步骤3：初始化全局答案 ans

ans赋值为系统最大整数math.MaxInt，作为最小值的初始无穷大占位，后续路径异或结果会不断更小覆盖它。

步骤4：定义递归DFS函数（反向回溯逻辑）

函数入参：i,j,xor

•i,j：当前递归所在网格坐标（初始调用是终点m-1,n-1）；

•xor：从终点往回走到当前格子前，已经累积的异或中间值（初始调用传0）。

DFS内部完整执行分支拆解分支1：提前终止剪枝条件，直接返回不继续递归

满足任意一条就退出当前递归：

1.ans == 0：已经找到异或等于0的最优解，不可能存在更小值，全部搜索停止；

2.i < 0 或 j < 0：反向回溯走出网格边界，非法坐标；

3.vis[i][j][xor] == true：当前坐标+当前异或值组合之前搜过，重复状态，无需重复遍历。

分支2：标记当前状态为已访问

如果没有触发提前终止，立刻设置vis[i][j][xor] = true，记录该(i,j,xor)状态已处理，防止其他路径再次进入相同状态造成重复计算。

分支3：把当前格子的值并入累积异或

执行xor ^= grid[i][j]：反向回溯时，每走到一个格子，就要把该格子数字参与异或运算，和正向路径所有数字异或结果完全等价。

原理：异或满足交换律、结合律，正向从起点一路异或到终点 = 反向从终点一路异或到起点。

分支4：判断是否抵达起点，更新最小答案

如果当前坐标i==0 && j==0，说明完整走完一条合法路径（从终点反向回到起点）：
用min(ans, xor)更新全局最小值ans，当前递归结束return。

分支5：反向递归两个合法前序格子

正向只能向右、向下走，反向回溯就只能向上、向左走，分别发起两层递归：

1. 向上走一格：调用dfs(i-1, j, xor)；

2. 向左走一格：调用dfs(i, j-1, xor)；
递归结束后当前函数出栈，回溯上层。

步骤5：启动DFS入口

从右下角终点开始反向搜索：dfs(m-1, n-1, 0)，初始累积异或值为0。

步骤6：返回最终最小异或结果

所有递归全部执行完毕后，全局变量ans存储所有合法路径的最小异或值，函数返回ans。

步骤7：main函数测试流程

1. 定义测试矩阵[[1,2],[3,4]]；

2. 调用minCost函数计算最小异或；

3. 打印输出结果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存储，仅算法额外开辟空间）

1. 三维vis数组空间：m × n × (orAll+1)，最大占用1000 × 1024布尔空间；

2. DFS递归栈深度：最长路径格子数为m+n-1（一路向下再一路向右），m、n最大1000但mn≤1000，栈深最多1000级；

3. 临时变量、循环变量均为常数空间，可忽略。

总额外空间复杂度：O(m × n × C)，C=1024，由三维访问数组主导，递归栈空间远小于数组空间，可合并计入该项。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
)

 func minCost(grid [][]int)int {
    m, n := len(grid), len(grid[0])
    // 异或和不会超过所有元素的 OR
    orAll := 0
    for _, row := range grid {
        for _, x := range row {
            orAll |= x
        }
    }

     vis := make([][][]bool, m)
    for i := range vis {
        vis[i] = make([][]bool, n)
        for j := range vis[i] {
            vis[i][j] = make([]bool, orAll+1)
        }
    }
    ans := math.MaxInt

     var dfs func(int, int, int)
    dfs = func(i, j, xor int) {
        // 最优性剪枝：如果答案已经最小（等于 0），那么不再搜索
        if ans == 0 || i < 0 || j < 0 || vis[i][j][xor] {
            return
        }
        vis[i][j][xor] = true
        xor ^= grid[i][j]
        if i == 0 && j == 0 {
            ans = min(ans, xor)
            return
        }
        dfs(i-1, j, xor)
        dfs(i, j-1, xor)
    }

     dfs(m-1, n-1, 0)
    return ans
}

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

2026-07-16：网格图中最小异或路径。用go语言，给定一个大小为 m × n 的二维整数矩阵 grid。你需要从左上角单元格 (0,0) 出发，走到右下

Python完整代码如下：

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

 import sys

 def minCost(grid):
    m, n = len(grid), len(grid[0])
    # 计算所有元素的按位或，作为异或和的上界
    or_all = 0
    for row in grid:
        for x in row:
            or_all |= x

     # visited[i][j][xor] 表示状态 (i, j, xor) 是否已被访问
    visited = [[[False] * (or_all + 1) for _ in range(n)] for _ in range(m)]
    ans = float('inf')

     sys.setrecursionlimit(1000000)  # 防止递归深度过大

     def dfs(i, j, xor):
        nonlocal ans
        # 最优性剪枝：答案已为 0 无需继续
        if ans == 0 or i < 0 or j < 0 or visited[i][j][xor]:
            return
        visited[i][j][xor] = True
        xor ^= grid[i][j]          # 累积当前格子的值
        if i == 0 and j == 0:      # 到达左上角，更新答案
            ans = min(ans, xor)
            return
        dfs(i - 1, j, xor)         # 向上移动
        dfs(i, j - 1, xor)         # 向左移动

     dfs(m - 1, n - 1, 0)           # 从右下角开始
    return ans

 if __name__ == "__main__":
    grid = [[1, 2], [3, 4]]
    result = minCost(grid)
    print(result)

2026-07-16：网格图中最小异或路径。用go语言，给定一个大小为 m × n 的二维整数矩阵 grid。你需要从左上角单元格 (0,0) 出发，走到右下

C++完整代码如下：

  

  

  

  

using namespace std;


 int minCost(vector 
 
 int 
 >>& grid) { 
 
 
      
 int 
  m = grid.size(); 
 
 
      
 int 
  n = grid[ 
 0 
 ].size(); 
 
 
 
 
      
 // 计算所有元素的按位或，作为异或和的上界 
 
 
      
 int 
  orAll =  
 0 
 ; 
 
 
      
 for 
  ( 
 const 
  auto& row : grid) { 
 
 
          
 for 
  ( 
 int 
  x : row) { 
 
 
             orAll |= x; 
 
 
         } 
 
 
     } 
 
 
 
 
      
 // visited[i][j][xor] 表示状态是否已经访问过 
 
 
     vector 
 
 bool 
 >>> vis( 
 
 
         m, vector 
 
 bool 
 >>(n, vector< 
 bool 
 >(orAll +  
 1 
 ,  
 false 
 )) 
 
 
         ); 
 
 
 
 
      
 int 
  ans = INT_MAX; 
 
 
 
 
      
 // 递归 DFS，使用 std::function 支持 lambda 自引用 
 
 
     function 
 
 int 
 ,  
 int 
 ,  
 int 
 )> dfs = [&]( 
 int 
  i,  
 int 
  j,  
 int 
  xorVal) { 
 
 
          
 // 最优性剪枝 + 边界检查 + 状态判重（短路保证安全） 
 
 
          
 if 
  (ans ==  
 0 
  || i <  
 0 
  || j <  
 0 
  || vis[i][j][xorVal]) { 
 
 
              
 return 
 ; 
 
 
         } 
 
 
         vis[i][j][xorVal] =  
 true 
 ; 
 
 
         xorVal ^= grid[i][j];           
 // 累加当前格子的值 
 
 
 
 
          
 if 
  (i ==  
 0 
  && j ==  
 0 
 ) {         
 // 到达起点，更新答案 
 
 
             ans = min(ans, xorVal); 
 
 
              
 return 
 ; 
 
 
         } 
 
 
         dfs(i -  
 1 
 , j, xorVal);          
 // 向上走 
 
 
         dfs(i, j -  
 1 
 , xorVal);          
 // 向左走 
 
 
     }; 
 
 
 
 
     dfs(m -  
 1 
 , n -  
 1 
 ,  
 0 
 );               
 // 从右下角开始搜索 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector 
 
 int 
 >> grid = {{ 
 1 
 ,  
 2 
 }, { 
 3 
 ,  
 4 
 }}; 
 
 
     cout << minCost(grid) << endl; 
 
 
      
 return 
 0 
 ; 
 
 
 }