题目描述

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

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

• 每一步你可以向右或者向下走，也就是如果格子存在的话，可以从格子 (i, j) 走到格子 (i, j + 1) 或者格子 (i + 1, j)。
• 路径上经过的所有数字 XOR 异或值必须 等于 k。

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

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

样例

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

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

输出：5

解释：

5 条路径分别为：

(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2) → (2, 3)
(0, 0) → (1, 0) → (1, 1) → (2, 1) → (2, 2) → (2, 3)
(0, 0) → (1, 0) → (1, 1) → (1, 2) → (1, 3) → (2, 3)
(0, 0) → (0, 1) → (1, 1) → (1, 2) → (2, 2) → (2, 3)
(0, 0) → (0, 1) → (0, 2) → (1, 2) → (2, 2) → (2, 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

算法

(动态规划) $O(mnk)$

1. 设状态 $f(i, j, t)$ 表示到达格子 $(i, j)$，且路径的异或值为 $t$ 的方案数。
2. 初始时，$f(0, 0, grid(0, 0)) = 1$，其余为 $0$。
3. 转移时，对于 $f(i, j, t)$，如果 $i < m - 1$，则可以转移到 $f(i + 1, j, t \text{ XOR } grid(i + 1, j))$；如果 $j < n - 1$，则可以转移到 $f(i, j + 1, t \text{ XOR } grid(i, j + 1))$。
4. 最终答案为 $f(m - 1, n - 1, k)$。

时间复杂度

• 动态规划的状态数为 $O(mnK)$，转移时间为常数，故总时间复杂度为 $O(mnK)$。其中 $K$ 为 $16$。

空间复杂度

• 需要 $O(mnK)$ 的额外空间存储状态。

C++ 代码

const int N = 300, K = 16;
const int mod = 1000000007;

class Solution {
private:
    int f[N][N][K];

    inline void add(int &x, int y) {
        x = (x + y) % mod;
    }

public:
    int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
        const int m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                memset(f[i][j], 0, sizeof(f[i][j]));

        f[0][0][grid[0][0]] = 1;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                for (int t = 0; t < K; t++) {
                    if (i < m - 1)
                        add(f[i + 1][j][t ^ grid[i + 1][j]], f[i][j][t]);

                    if (j < n - 1)
                        add(f[i][j + 1][t ^ grid[i][j + 1]], f[i][j][t]);
                }

        return f[m - 1][n - 1][k];
    }
};