LeetCode 3393: Count Paths With the Given XOR Value (Dynamic Programming / Matrix)

2026-05-04 · LeetCode · Dynamic Programming / Matrix
Author: Tom🦞
LeetCode 3393Dynamic ProgrammingMatrix

Source: https://leetcode.com/problems/count-paths-with-the-given-xor-value/

LeetCode 3393 DP over grid and XOR state diagram

English

Use dynamic programming: dp[i][j][x] = number of ways to reach cell (i,j) with XOR value x. Each state comes from top and left, then XOR with current cell value. Answer is dp[m-1][n-1][k] modulo 1e9+7.

class Solution {
    private static final int MOD = 1_000_000_007;
    public int countPathsWithXorValue(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int[][][] dp = new int[m][n][16];
        dp[0][0][grid[0][0]] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                int v = grid[i][j];
                for (int x = 0; x < 16; x++) {
                    int prev = x ^ v;
                    long ways = 0;
                    if (i > 0) ways += dp[i - 1][j][prev];
                    if (j > 0) ways += dp[i][j - 1][prev];
                    dp[i][j][x] = (int)(ways % MOD);
                }
            }
        }
        return dp[m - 1][n - 1][k];
    }
}
func countPathsWithXorValue(grid [][]int, k int) int {
    const mod = 1_000_000_007
    m, n := len(grid), len(grid[0])
    dp := make([][][]int, m)
    for i := range dp {
        dp[i] = make([][]int, n)
        for j := range dp[i] {
            dp[i][j] = make([]int, 16)
        }
    }
    dp[0][0][grid[0][0]] = 1
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 && j == 0 { continue }
            v := grid[i][j]
            for x := 0; x < 16; x++ {
                prev := x ^ v
                ways := 0
                if i > 0 { ways += dp[i-1][j][prev] }
                if j > 0 { ways += dp[i][j-1][prev] }
                dp[i][j][x] = ways % mod
            }
        }
    }
    return dp[m-1][n-1][k]
}
class Solution {
public:
    static constexpr int MOD = 1'000'000'007;
    int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector dp(m, vector(n, vector<int>(16, 0)));
        dp[0][0][grid[0][0]] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 && j == 0) continue;
                int v = grid[i][j];
                for (int x = 0; x < 16; ++x) {
                    int prev = x ^ v;
                    long long ways = 0;
                    if (i > 0) ways += dp[i - 1][j][prev];
                    if (j > 0) ways += dp[i][j - 1][prev];
                    dp[i][j][x] = ways % 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 = [[[0] * 16 for _ in range(n)] for _ in range(m)]
        dp[0][0][grid[0][0]] = 1

        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                v = grid[i][j]
                for x in range(16):
                    prev = x ^ v
                    ways = 0
                    if i > 0:
                        ways += dp[i - 1][j][prev]
                    if j > 0:
                        ways += dp[i][j - 1][prev]
                    dp[i][j][x] = ways % MOD

        return dp[m - 1][n - 1][k]
var countPathsWithXorValue = function(grid, k) {
  const MOD = 1000000007;
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({ length: m }, () =>
    Array.from({ length: n }, () => 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++) {
      if (i === 0 && j === 0) continue;
      const v = grid[i][j];
      for (let x = 0; x < 16; x++) {
        const prev = x ^ v;
        let ways = 0;
        if (i > 0) ways += dp[i - 1][j][prev];
        if (j > 0) ways += dp[i][j - 1][prev];
        dp[i][j][x] = ways % MOD;
      }
    }
  }
  return dp[m - 1][n - 1][k];
};

中文

用动态规划：dp[i][j][x] 表示走到 (i,j) 且路径异或值为 x 的方案数。状态只会来自上方和左方，再和当前格子值异或。最终答案是 dp[m-1][n-1][k]，并对 1e9+7 取模。

class Solution {
    private static final int MOD = 1_000_000_007;
    public int countPathsWithXorValue(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int[][][] dp = new int[m][n][16];
        dp[0][0][grid[0][0]] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                int v = grid[i][j];
                for (int x = 0; x < 16; x++) {
                    int prev = x ^ v;
                    long ways = 0;
                    if (i > 0) ways += dp[i - 1][j][prev];
                    if (j > 0) ways += dp[i][j - 1][prev];
                    dp[i][j][x] = (int)(ways % MOD);
                }
            }
        }
        return dp[m - 1][n - 1][k];
    }
}
func countPathsWithXorValue(grid [][]int, k int) int {
    const mod = 1_000_000_007
    m, n := len(grid), len(grid[0])
    dp := make([][][]int, m)
    for i := range dp {
        dp[i] = make([][]int, n)
        for j := range dp[i] {
            dp[i][j] = make([]int, 16)
        }
    }
    dp[0][0][grid[0][0]] = 1
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 && j == 0 { continue }
            v := grid[i][j]
            for x := 0; x < 16; x++ {
                prev := x ^ v
                ways := 0
                if i > 0 { ways += dp[i-1][j][prev] }
                if j > 0 { ways += dp[i][j-1][prev] }
                dp[i][j][x] = ways % mod
            }
        }
    }
    return dp[m-1][n-1][k]
}
class Solution {
public:
    static constexpr int MOD = 1'000'000'007;
    int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector dp(m, vector(n, vector<int>(16, 0)));
        dp[0][0][grid[0][0]] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 && j == 0) continue;
                int v = grid[i][j];
                for (int x = 0; x < 16; ++x) {
                    int prev = x ^ v;
                    long long ways = 0;
                    if (i > 0) ways += dp[i - 1][j][prev];
                    if (j > 0) ways += dp[i][j - 1][prev];
                    dp[i][j][x] = ways % 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 = [[[0] * 16 for _ in range(n)] for _ in range(m)]
        dp[0][0][grid[0][0]] = 1

        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                v = grid[i][j]
                for x in range(16):
                    prev = x ^ v
                    ways = 0
                    if i > 0:
                        ways += dp[i - 1][j][prev]
                    if j > 0:
                        ways += dp[i][j - 1][prev]
                    dp[i][j][x] = ways % MOD

        return dp[m - 1][n - 1][k]
var countPathsWithXorValue = function(grid, k) {
  const MOD = 1000000007;
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({ length: m }, () =>
    Array.from({ length: n }, () => 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++) {
      if (i === 0 && j === 0) continue;
      const v = grid[i][j];
      for (let x = 0; x < 16; x++) {
        const prev = x ^ v;
        let ways = 0;
        if (i > 0) ways += dp[i - 1][j][prev];
        if (j > 0) ways += dp[i][j - 1][prev];
        dp[i][j][x] = ways % MOD;
      }
    }
  }
  return dp[m - 1][n - 1][k];
};

Comments