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

福大大架构师每日一题

发布于 2026-07-16 21:57:23

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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)
}

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)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <climits>
#include <functional>
using namespace std;

int minCost(vector<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<vector<vector<bool>>> vis(
        m, vector<vector<bool>>(n, vector<bool>(orAll + 1, false))
        );

    int ans = INT_MAX;

    // 递归 DFS，使用 std::function 支持 lambda 自引用
    function<void(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<vector<int>> grid = {{1, 2}, {3, 4}};
    cout << minCost(grid) << endl;
    return0;
}