Medium

题目描述

给你一个大小为 m x n 的二维整数数组 grid，同时给你一个整数 k。

你的任务是计算从左上角单元格 (0, 0) 到右下角单元格 (m - 1, n - 1) 的路径数量，需要满足以下约束条件：

  • 你只能向右或向下移动。形式上，从单元格 (i, j) 你可以移动到单元格 (i, j + 1) 或 (i + 1, j)（如果目标单元格存在）。
  • 路径上所有数字的异或值必须等于 k。

返回满足条件的路径总数。

由于答案可能很大，返回结果对 10^9 + 7 取模。

示例 1：

输入：grid = [[2, 1, 5], [7, 10, 0], [12, 6, 4]], k = 11
输出：3
解释：
3 条路径分别是：
- (0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2)
- (0, 0) → (1, 0) → (1, 1) → (1, 2) → (2, 2)
- (0, 0) → (0, 1) → (1, 1) → (2, 1) → (2, 2)

示例 2：

输入：grid = [[1, 3, 3, 3], [0, 3, 3, 2], [3, 0, 1, 1]], k = 2
输出：5

示例 3：

输入：grid = [[1, 1, 1, 2], [3, 0, 3, 2], [3, 0, 2, 2]], k = 10
输出：0

约束条件：

  • 1 <= m == grid.length <= 300
  • 1 <= n == grid[r].length <= 300
  • 0 <= grid[r][c] < 16
  • 0 <= k < 16

解题思路

这是一道典型的动态规划问题，需要在路径规划中加入异或值的约束。

核心思路：

  1. 定义状态：dp[i][j][xor] 表示从 (0,0) 到达位置 (i,j) 且路径异或值为 xor 的方案数
  2. 状态转移：当前位置可以从上方或左方到达，异或值需要考虑当前格子的值
  3. 初始化：起始位置 dp[0][0][grid[0][0]] = 1
  4. 最终答案：dp[m-1][n-1][k]

优化考虑： 由于异或值的范围很小（0-15），可以用三维DP直接求解。异或运算的性质使得 a ^ b ^ c = (a ^ b) ^ c，这样我们可以逐步计算路径的异或值。

状态转移方程为：

  • dp[i][j][xor] += dp[i-1][j][xor ^ grid[i][j]]（从上方来）
  • dp[i][j][xor] += dp[i][j-1][xor ^ grid[i][j]]（从左方来）

时间复杂度为 O(m×n×16)，空间复杂度也是 O(m×n×16)。

代码实现

class Solution {
public:
    int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
        const int MOD = 1e9 + 7;
        int m = grid.size(), n = grid[0].size();
        
        // dp[i][j][xor] = number of paths to (i,j) with XOR value = xor
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(16, 0)));
        
        // Initialize starting position
        dp[0][0][grid[0][0]] = 1;
        
        // Fill the dp table
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int xor_val = 0; xor_val < 16; xor_val++) {
                    if (dp[i][j][xor_val] == 0) continue;
                    
                    // Move right
                    if (j + 1 < n) {
                        int new_xor = xor_val ^ grid[i][j + 1];
                        dp[i][j + 1][new_xor] = (dp[i][j + 1][new_xor] + dp[i][j][xor_val]) % MOD;
                    }
                    
                    // Move down
                    if (i + 1 < m) {
                        int new_xor = xor_val ^ grid[i + 1][j];
                        dp[i + 1][j][new_xor] = (dp[i + 1][j][new_xor] + dp[i][j][xor_val]) % MOD;
                    }
                }
            }
        }
        
        return dp[m - 1][n - 1][k];
    }
};

class Solution:
    def countPathsWithXorValue(self, grid: List[List[int]], k: int) -> int:
        MOD = 10**9 + 7
        m, n = len(grid), len(grid[0])
        
        # dp[i][j][xor] = number of paths to (i,j) with XOR value = xor
        dp = [[[0] * 16 for _ in range(n)] for _ in range(m)]
        
        # Initialize starting position
        dp[0][0][grid[0][0]] = 1
        
        # Fill the dp table
        for i in range(m):
            for j in range(n):
                for xor_val in range(16):
                    if dp[i][j][xor_val] == 0:
                        continue
                    
                    # Move right
                    if j + 1 < n:
                        new_xor = xor_val ^ grid[i][j + 1]
                        dp[i][j + 1][new_xor] = (dp[i][j + 1][new_xor] + dp[i][j][xor_val]) % MOD
                    
                    # Move down
                    if i + 1 < m:
                        new_xor = xor_val ^ grid[i + 1][j]
                        dp[i + 1][j][new_xor] = (dp[i + 1][j][new_xor] + dp[i][j][xor_val]) % MOD
        
        return dp[m - 1][n - 1][k]

public class Solution {
    public int CountPathsWithXorValue(int[][] grid, int k) {
        const int MOD = 1000000007;
        int m = grid.Length, n = grid[0].Length;
        
        // dp[i][j][xor] = number of paths to (i,j) with XOR value = xor
        int[,,] dp = new int[m, n, 16];
        
        // Initialize starting position
        dp[0, 0, grid[0][0]] = 1;
        
        // Fill the dp table
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int xor_val = 0; xor_val < 16; xor_val++) {
                    if (dp[i, j, xor_val] == 0) continue;
                    
                    // Move right
                    if (j + 1 < n) {
                        int new_xor = xor_val ^ grid[i][j + 1];
                        dp[i, j + 1, new_xor] = (dp[i, j + 1, new_xor] + dp[i, j, xor_val]) % MOD;
                    }
                    
                    // Move down
                    if (i + 1 < m) {
                        int new_xor = xor_val ^ grid[i + 1][j];
                        dp[i + 1, j, new_xor] = (dp[i + 1, j, new_xor] + dp[i, j, xor_val]) % MOD;
                    }
                }
            }
        }
        
        return dp[m - 1, n - 1, k];
    }
}

var countPathsWithXorValue = function(grid, k) {
    const MOD = 1000000007;
    const m = grid.length;
    const n = grid[0].length;
    
    // dp[i][j][xor] = number of paths to (i,j) with XOR value = xor
    const dp = Array(m).fill().map(() => 
        Array(n).fill().map(() => Array(16).fill(0))
    );
    
    dp[0][0][grid[0][0]] = 1;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            for (let xor = 0; xor < 16; xor++) {
                if (dp[i][j][xor] === 0) continue;
                
                // Move right
                if (j + 1 < n) {
                    const newXor = xor ^ grid[i][j + 1];
                    dp[i][j + 1][newXor] = (dp[i][j + 1][newXor] + dp[i][j][xor]) % MOD;
                }
                
                // Move down
                if (i + 1 < m) {
                    const newXor = xor ^ grid[i + 1][j];
                    dp[i + 1][j][newXor] = (dp[i + 1][j][newXor] + dp[i][j][xor]) % MOD;
                }
            }
        }
    }
    
    return dp[m - 1][n - 1][k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m×n×16)需要遍历每个位置和每种可能的异或值
空间复杂度O(m×n×16)三维DP数组存储所有状态

相关题目