Problem

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 10^9 + 7.

Examples

Example 1

1
2
3
4
5
6
7

Input:d = [[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

1
2
3
4
5
6
7
8
9

Input:d = [[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

1
2

Input:d = [[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

Method 1 – Dynamic Programming (DP) with XOR State

Intuition

Since the grid values and k are small (0-15), we can use DP to track the number of ways to reach each cell with a given XOR value. For each cell, the number of ways to reach it with XOR x is the sum of the ways to reach the cell above and the cell to the left with XOR (x ^ grid[i][j]).

Approach

  1. Let dp[i][j][x] be the number of ways to reach cell (i, j) with XOR value x.
  2. Initialize dp[0][0][grid[0][0]] = 1.
  3. For each cell (i, j), for each possible XOR value x (0 to 15):
    1. If i > 0, add dp[i-1][j][x ^ grid[i][j]] to dp[i][j][x].
    2. If j > 0, add dp[i][j-1][x ^ grid[i][j]] to dp[i][j][x].
  4. The answer is dp[m-1][n-1][k].
  5. Return the answer modulo 10^9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length, MOD = 1000000007;
        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++) {
                for (int x = 0; x < 16; x++) {
                    if (i > 0) dp[i][j][x] = (dp[i][j][x] + dp[i-1][j][x ^ grid[i][j]]) % MOD;
                    if (j > 0) dp[i][j][x] = (dp[i][j][x] + dp[i][j-1][x ^ grid[i][j]]) % MOD;
                }
            }
        }
        return dp[m-1][n-1][k];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def numberOfPaths(self, grid: list[list[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        MOD = 10**9 + 7
        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):
                for x in range(16):
                    if i > 0:
                        dp[i][j][x] = (dp[i][j][x] + dp[i-1][j][x ^ grid[i][j]]) % MOD
                    if j > 0:
                        dp[i][j][x] = (dp[i][j][x] + dp[i][j-1][x ^ grid[i][j]]) % MOD
        return dp[m-1][n-1][k]

Complexity

  • ⏰ Time complexity: O(m * n * 16), since we process each cell and each possible XOR value.
  • 🧺 Space complexity: O(m * n * 16), for the DP table.