日期: 2026年10月28日

目标

给你一个大小为 m * n 的二维整数数组 grid。

你从 左上角 的单元格 (0, 0) 出发，想要到达 右下角 的单元格 (m - 1, n - 1)。

在每一步中，你 可以 向右或向下 移动。

路径的 代价 定义为该路径上所有单元格（包括 起点和终点）的值的 按位异或。

返回从 (0, 0) 到 (m - 1, n - 1) 的所有有效路径中 最小 的可能异或值。

示例 1：

输入： 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。

示例 2：

输入： grid = [[6,7],[5,8]]
输出： 9
解释：
有两条有效路径：
(0, 0) → (0, 1) → (1, 1)，异或值为：6 XOR 7 XOR 8 = 9
(0, 0) → (1, 0) → (1, 1)，异或值为：6 XOR 5 XOR 8 = 11
所有有效路径中的最小异或值为 9。

示例 3：

输入： grid = [[2,7,5]]
输出： 0
解释：
只有一条有效路径：
(0, 0) → (0, 1) → (0, 2)，异或值为：2 XOR 7 XOR 5 = 0
这条路径的异或值为 0，这是可能达到的最小值。

说明：

• 1 <= m == grid.length <= 1000
• 1 <= n == grid[i].length <= 1000
• m * n <= 1000
• 0 <= grid[i][j] <= 1023​

思路

有一个 m x n 的网格，允许向下或向右移动，求从左上到右下的路径上元素异或和的最小值。

注意到 m * n <= 1000，可以记忆路径到达 (i,j) 时的异或和，如果该状态已经访问过则跳过。

代码

/**
 * @date 2026-10-28 9:18
 */
public class MinCost3882 {

    public int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][][] mem = new boolean[m][n][1024];
        dfs(0, 0, 0, grid, mem);
        for (int i = 0; i < 1024; i++) {
            if (mem[m - 1][n - 1][i]) {
                return i;
            }
        }
        return -1;
    }

    public void dfs(int i, int j, int xor, int[][] grid, boolean[][][] mem) {
        int m = grid.length;
        int n = grid[0].length;
        if (i >= m || j >= n) {
            return;
        }
        xor ^= grid[i][j];
        if (mem[i][j][xor]) {
            return;
        }
        mem[i][j][xor] = true;
        dfs(i + 1, j, xor, grid, mem);
        dfs(i, j + 1, xor, grid, mem);
    }

}

性能