列表

详情

3393. 统计异或值为给定值的路径数目

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

你的任务是统计满足以下 条件 且从左上格子 (0, 0) 出发到达右下格子 (m - 1, n - 1) 的路径数目：

请你返回满足上述条件的路径总数。

由于答案可能很大，请你将答案对 109 + 7 取余 后返回。

 

示例 1：

输入：grid = [[2, 1, 5], [7, 10, 0], [12, 6, 4]], k = 11

输出：3

解释：

3 条路径分别为：

示例 2：

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

输出：5

解释：

5 条路径分别为：

示例 3：

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

输出：0

 

提示：

相似题目

统计异或值在范围内的数对有多少

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int countPathsWithXorValue(vector<vector<int>>& grid, int k) { } };

java 解法, 执行用时: 25 ms, 内存消耗: 54.7 MB, 提交时间: 2024-12-30 23:57:02 

class Solution {
    public int countPathsWithXorValue(int[][] grid, int k) {
        final int MOD = 1_000_000_007;
        int mx = 0;
        for (int[] row : grid) {
            for (int val : row) {
                mx = Math.max(mx, val);
            }
        }
        int u = 1 << (32 - Integer.numberOfLeadingZeros(mx));
        if (k >= u) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
        int[][][] f = new int[m + 1][n + 1][u];
        f[1][1][grid[0][0]] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int val = grid[i][j];
                for (int x = 0; x < u; x++) {
                    f[i + 1][j + 1][x] += (f[i + 1][j][x ^ val] + f[i][j + 1][x ^ val]) % MOD;
                }
            }
        }
        return f[m][n][k];
    }
}

golang 解法, 执行用时: 45 ms, 内存消耗: 19.8 MB, 提交时间: 2024-12-30 23:56:40 

func countPathsWithXorValue(grid [][]int, k int) int {
	const mod = 1_000_000_007
	mx := 0
	for _, row := range grid {
		mx = max(mx, slices.Max(row))
	}
	u := 1 << bits.Len(uint(mx))
	if k >= u {
		return 0
	}

	m, n := len(grid), len(grid[0])
	f := make([][][]int, m+1)
	for i := range f {
		f[i] = make([][]int, n+1)
		for j := range f[i] {
			f[i][j] = make([]int, u)
		}
	}
	f[1][1][grid[0][0]] = 1
	for i, row := range grid {
		for j, val := range row {
			for x := range u {
				f[i+1][j+1][x] += (f[i+1][j][x^val] + f[i][j+1][x^val]) % mod
			}
		}
	}
	return f[m][n][k]
}

cpp 解法, 执行用时: 270 ms, 内存消耗: 93.4 MB, 提交时间: 2024-12-30 23:56:24 

class Solution {
public:
    int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
        const int MOD = 1'000'000'007;
        int mx = 0;
        for (auto& row : grid) {
            mx = max(mx, ranges::max(row));
        }
        int u = 1 << bit_width((unsigned) mx);
        if (k >= u) {
            return 0;
        }

        int m = grid.size(), n = grid[0].size();
        vector memo(m, vector(n, vector<int>(u, -1)));
        auto dfs = [&](this auto&& dfs, int i, int j, int x) -> int {
            if (i < 0 || j < 0) {
                return 0;
            }
            int val = grid[i][j];
            if (i == 0 && j == 0) {
                return x == val;
            }
            int& res = memo[i][j][x]; // 注意这里是引用
            if (res != -1) {
                return res;
            }
            return res = (dfs(i, j - 1, x ^ val) + dfs(i - 1, j, x ^ val)) % MOD;
        };
        return dfs(m - 1, n - 1, k);
    }


    int countPathsWithXorValue2(vector<vector<int>>& grid, int k) {
        const int MOD = 1'000'000'007;
        int mx = 0;
        for (auto& row : grid) {
            mx = max(mx, ranges::max(row));
        }
        int u = 1 << bit_width((unsigned) mx);
        if (k >= u) {
            return 0;
        }

        int m = grid.size(), n = grid[0].size();
        vector f(m + 1, vector(n + 1, vector<int>(u)));
        f[1][1][grid[0][0]] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int val = grid[i][j];
                for (int x = 0; x < u; x++) {
                    f[i + 1][j + 1][x] += (f[i + 1][j][x ^ val] + f[i][j + 1][x ^ val]) % MOD;
                }
            }
        }
        return f[m][n][k];
    }
};

python3 解法, 执行用时: 3123 ms, 内存消耗: 766.5 MB, 提交时间: 2024-12-30 23:55:50 

class Solution:
    def countPathsWithXorValue(self, grid: List[List[int]], k: int) -> int:
        MOD = 1_000_000_007
        @cache
        def dfs(i: int, j: int, x: int) -> int:
            if i < 0 or j < 0:
                return 0
            val = grid[i][j]
            if i == 0 and j == 0:
                return 1 if x == val else 0
            return (dfs(i, j - 1, x ^ val) + dfs(i - 1, j, x ^ val)) % MOD
        return dfs(len(grid) - 1, len(grid[0]) - 1, k)


    def countPathsWithXorValue2(self, grid: List[List[int]], k: int) -> int:
        MOD = 1_000_000_007
        u = 1 << max(map(max, grid)).bit_length()
        if k >= u:
            return 0

        m, n = len(grid), len(grid[0])
        f = [[[0] * u for _ in range(n + 1)] for _ in range(m + 1)]
        f[1][1][grid[0][0]] = 1
        for i, row in enumerate(grid):
            for j, val in enumerate(row):
                for x in range(u):
                    f[i + 1][j + 1][x] += (f[i + 1][j][x ^ val] + f[i][j + 1][x ^ val]) % MOD
        return f[m][n][k]

上一题

© 2025 leetcode.cn