Medium

题目描述

给你一个大小为 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

解题思路

这是一个典型的动态规划问题，但与普通的路径问题不同，我们需要跟踪所有可能的异或值。

核心思路：

  1. 定义状态：dp[i][j] 表示到达位置 (i,j) 时所有可能的异或值集合
  2. 状态转移：位置 (i,j) 的异或值集合由上方 (i-1,j) 和左方 (i,j-1) 转移而来
  3. 转移方程：对于上方或左方的每个异或值 xor_val，新的异或值为 xor_val ^ grid[i][j]

算法步骤：

  1. 初始化：dp[0][0] 只包含 grid[0][0]
  2. 处理第一行和第一列，每个位置只有一种到达方式
  3. 对于其他位置，合并来自上方和左方的所有可能异或值
  4. 返回 dp[m-1][n-1] 中的最小值

优化考虑： 由于约束条件 m * n <= 1000 且 grid[i][j] <= 1023，理论上最多有 1024 种不同的异或值，使用集合存储是可行的。

推荐解法： 使用集合存储每个位置的所有可能异或值，空间和时间复杂度都是可接受的。

代码实现

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<unordered_set<int>>> dp(m, vector<unordered_set<int>>(n));
        
        // 初始化起点
        dp[0][0].insert(grid[0][0]);
        
        // 处理第一行
        for (int j = 1; j < n; j++) {
            for (int xor_val : dp[0][j-1]) {
                dp[0][j].insert(xor_val ^ grid[0][j]);
            }
        }
        
        // 处理第一列
        for (int i = 1; i < m; i++) {
            for (int xor_val : dp[i-1][0]) {
                dp[i][0].insert(xor_val ^ grid[i][0]);
            }
        }
        
        // 处理其他位置
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 从上方转移
                for (int xor_val : dp[i-1][j]) {
                    dp[i][j].insert(xor_val ^ grid[i][j]);
                }
                // 从左方转移
                for (int xor_val : dp[i][j-1]) {
                    dp[i][j].insert(xor_val ^ grid[i][j]);
                }
            }
        }
        
        // 返回终点的最小异或值
        return *min_element(dp[m-1][n-1].begin(), dp[m-1][n-1].end());
    }
};

class Solution:
    def minCost(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[set() for _ in range(n)] for _ in range(m)]
        
        # 初始化起点
        dp[0][0].add(grid[0][0])
        
        # 处理第一行
        for j in range(1, n):
            for xor_val in dp[0][j-1]:
                dp[0][j].add(xor_val ^ grid[0][j])
        
        # 处理第一列
        for i in range(1, m):
            for xor_val in dp[i-1][0]:
                dp[i][0].add(xor_val ^ grid[i][0])
        
        # 处理其他位置
        for i in range(1, m):
            for j in range(1, n):
                # 从上方转移
                for xor_val in dp[i-1][j]:
                    dp[i][j].add(xor_val ^ grid[i][j])
                # 从左方转移
                for xor_val in dp[i][j-1]:
                    dp[i][j].add(xor_val ^ grid[i][j])
        
        # 返回终点的最小异或值
        return min(dp[m-1][n-1])

public class Solution {
    public int MinCost(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        var dp = new HashSet<int>[m, n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = new HashSet<int>();
            }
        }
        
        // 初始化起点
        dp[0, 0].Add(grid[0][0]);
        
        // 处理第一行
        for (int j = 1; j < n; j++) {
            foreach (int xorVal in dp[0, j-1]) {
                dp[0, j].Add(xorVal ^ grid[0][j]);
            }
        }
        
        // 处理第一列
        for (int i = 1; i < m; i++) {
            foreach (int xorVal in dp[i-1, 0]) {
                dp[i, 0].Add(xorVal ^ grid[i][0]);
            }
        }
        
        // 处理其他位置
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 从上方转移
                foreach (int xorVal in dp[i-1, j]) {
                    dp[i, j].Add(xorVal ^ grid[i][j]);
                }
                // 从左方转移
                foreach (int xorVal in dp[i, j-1]) {
                    dp[i, j].Add(xorVal ^ grid[i][j]);
                }
            }
        }
        
        // 返回终点的最小异或值
        return dp[m-1, n-1].Min();
    }
}

var minCost = function(grid) {
    const m = grid.length, n = grid[0].length;
    const dp = Array(m).fill().map(() => Array(n).fill().map(() => new Set()));
    
    // 初始化起点
    dp[0][0].add(grid[0][0]);
    
    // 处理第一行
    for (let j = 1; j < n; j++) {
        for (const xorVal of dp[0][j-1]) {
            dp[0][j].add(xorVal ^ grid[0][j]);
        }
    }
    
    // 处理第一列
    for (let i = 1; i < m; i++) {
        for (const xorVal of dp[i-1][0]) {
            dp[i][0].add(xorVal ^ grid[i][0]);
        }
    }
    
    // 处理其他位置
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            // 从上方转移
            for (const xorVal of dp[i-1][j]) {
                dp[i][j].add(xorVal ^ grid[i][j]);
            }
            // 从左方转移
            for (const xorVal of dp[i][j-1]) {
                dp[i][j].add(xorVal ^ grid[i][j]);
            }
        }
    }
    
    // 返回终点的最小异或值
    return Math.min(...dp[m-1][n-1]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n × k)，其中 k 是每个位置可能的不同异或值数量。在最坏情况下 k ≤ 2^10 = 1024
空间复杂度O(m × n × k)，用于存储每个位置的所有可能异或值