3393. Count Paths With the Given XOR Value

You are given a 2D integer array grid with size m x n. You are also given an integer k.

Your task is to calculate the number of paths you can take from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1) satisfying the following constraints:

You can either move to the right or down. Formally, from the cell (i, j) you may move to the cell (i, j + 1) or to the cell (i + 1, j) if the target cell exists.
The XOR of all the numbers on the path must be equal to k.

Return the total number of such paths.

Since the answer can be very large, return the result modulo 109 + 7.

Example 1:

Input: grid = [[2, 1, 5], [7, 10, 0], [12, 6, 4]], k = 11

Output: 3

Explanation:

The 3 paths are:

(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)

Example 2:

Input: grid = [[1, 3, 3, 3], [0, 3, 3, 2], [3, 0, 1, 1]], k = 2

Output: 5

Explanation:

The 5 paths are:

(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)

Example 3:

Input: grid = [[1, 1, 1, 2], [3, 0, 3, 2], [3, 0, 2, 2]], k = 10

Output: 0

Constraints:

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

Solution:

DFS

由于值域范围小, 可以把路径的XOR值作为DP的第三个参数, 即定义$dfs(i, j, x)$, 表示从左上角$(0,0)$ 到 $(i, j - 1)$, 路径XOR值为x的方案数.

设左上角$(0,0)$到(i, j - 1)的路径XOR值为y, 那么必须满足 $$ y \oplus grid[i][j] =x $$ 即 $$ y = x \oplus grid[i][j] $$ 其中$\oplus$ 表示异或运算

分类讨论怎么到达$(i, j)$:

如果是从左边过来, 根据上文的公式有$dfs(i,j,x) = dfs(i, j - 1, x \oplus grid[i][j])$
如果是从上边过来, 则$dfs(i, j - 1, x \oplus grid[i][j]) + dfs(i - 1, j, x \oplus grid[x][y])$

倒序递归是为了方便后面1:1翻译成正序的递推

递归边界:

$dfs(-1, j, x) =dfs(i, - 1, x) = 0$ , 出界, 方案数为0
$dfs(0,0, grid[0][0] = 1)$, 其余$dfs(0,0,x) = 0$. 左上角$(0,0)$到它自己的方案数是1, 路径XOR值为$grid[0][0]$

递归入口: $dfs(m - 1, n - 1, k)$

细节:

设mx 为$grid[i][j]$的最大值, 其二进制长度为$L$

那么$2^L - 1$ 就是XOR能取到的最大值

如果$k > 2 ^L - 1$, 那么直接返回0.

p.s.: 也可以用所有$grid[i][j]$的OR, 作为XOR可以取到的最大值

DFS + Memo

class Solution {
    private static final int MOD = 1_000_000_007;
    int result;
    int n;
    int m;
    public int countPathsWithXorValue(int[][] grid, int k) {
        // right
        // down
        n = grid.length;
        m = grid[0].length;
        int cur = grid[0][0];
        Integer[][][] memo = new Integer[n][m][16];
        return dfs(0, 0, grid, k, cur, memo);

    }

    private int dfs(int x, int y, int[][] grid, int k, int cur, Integer[][][] memo){
        if (x < 0 || x >= n || y < 0 || y >= m){
            return 0;
        }

        if (x == n - 1 &&  y == m - 1){
            if (k == cur){
                return 1;

            }
            return 0;
        }
        if (memo[x][y][cur] != null){
            return memo[x][y][cur];
        }

        int path = 0;
        if (y + 1 < m){
            path = (path + dfs(x, y + 1, grid, k, cur ^ grid[x][y+1], memo)) % MOD;
        }

        if (x + 1  < n){
            path = (path + dfs(x + 1, y, grid, k, cur ^ grid[x+1][y], memo)) % MOD;
        }

        memo[x][y][cur] = path;
        return path;
    }
}


// TC: O(n*m*16)
// SC: O(n*m*16)

Reference

https://leetcode.cn/problems/count-paths-with-the-given-xor-value/solutions/3026905/wang-ge-tu-dpcong-ji-yi-hua-sou-suo-dao-k1bpm/