Skip to content

3393. Count Paths With the Given XOR Value 👍

Approach 1: Top-down

  • Time: $O(16mn) = O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
    constexpr int kMax = 15;
    const int m = grid.size();
    const int n = grid[0].size();
    vector<vector<vector<int>>> mem(
        m, vector<vector<int>>(n, vector<int>(kMax + 1, -1)));
    return count(grid, 0, 0, 0, k, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Return the number of paths from (i, j) to (m - 1, n - 1) with XOR value
  // `xors`.
  int count(const vector<vector<int>>& grid, int i, int j, int xors, int k,
            vector<vector<vector<int>>>& mem) {
    if (i == grid.size() || j == grid[0].size())
      return 0;
    xors ^= grid[i][j];
    if (i == grid.size() - 1 && j == grid[0].size() - 1)
      return xors == k ? 1 : 0;
    if (mem[i][j][xors] != -1)
      return mem[i][j][xors];
    const int right = count(grid, i, j + 1, xors, k, mem) % kMod;
    const int down = count(grid, i + 1, j, xors, k, mem) % kMod;
    return mem[i][j][xors] = (right + down) % kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int countPathsWithXorValue(int[][] grid, int k) {
    final int MAX = 15;
    final int m = grid.length;
    final int n = grid[0].length;
    Integer[][][] mem = new Integer[m][n][MAX + 1];
    return count(grid, 0, 0, 0, k, mem);
  }

  private static final int MOD = 1_000_000_007;

  // Return the number of paths from (i, j) to (m - 1, n - 1) with XOR value
  // `xors`.
  private int count(int[][] grid, int i, int j, int xors, int k, Integer[][][] mem) {
    if (i == grid.length || j == grid[0].length)
      return 0;
    xors ^= grid[i][j];
    if (i == grid.length - 1 && j == grid[0].length - 1)
      return xors == k ? 1 : 0;
    if (mem[i][j][xors] != null)
      return mem[i][j][xors];
    final int right = count(grid, i, j + 1, xors, k, mem) % MOD;
    final int down = count(grid, i + 1, j, xors, k, mem) % MOD;
    return mem[i][j][xors] = (right + down) % MOD;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def countPathsWithXorValue(self, grid: list[list[int]], k: int) -> int:
    MOD = 1_000_000_007
    m = len(grid)
    n = len(grid[0])

    @functools.lru_cache(None)
    def count(i: int, j: int, xors: int) -> int:
      """
      Return the number of paths from (i, j) to (m - 1, n - 1) with XOR value
      `xors`.
      """
      if i == m or j == n:
        return 0
      xors ^= grid[i][j]
      if i == m - 1 and j == n - 1:
        return int(xors == k)
      right = count(i, j + 1, xors)
      down = count(i + 1, j, xors)
      return (right + down) % MOD

    return count(0, 0, 0)

Approach 2: Bottom-up (reverse)

  • Time: $O(16mn) = O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
    constexpr int kMod = 1'000'000'007;
    constexpr int kMax = 15;
    const int m = grid.size();
    const int n = grid[0].size();
    // dp[i][j][xors] := the number of paths from (i, j) to (m - 1, n - 1) with
    // XOR value `xors`
    vector<vector<vector<int>>> dp(
        m, vector<vector<int>>(n, vector<int>(kMax + 1)));

    dp[m - 1][n - 1][grid[m - 1][n - 1]] = 1;

    for (int i = m - 1; i >= 0; --i)
      for (int j = n - 1; j >= 0; --j)
        for (int xors = 0; xors <= kMax; ++xors) {
          if (i - 1 >= 0) {
            const int newXor = xors ^ grid[i - 1][j];
            dp[i - 1][j][newXor] += dp[i][j][xors];
            dp[i - 1][j][newXor] %= kMod;
          }
          if (j - 1 >= 0) {
            const int newXor = xors ^ grid[i][j - 1];
            dp[i][j - 1][newXor] += dp[i][j][xors];
            dp[i][j - 1][newXor] %= kMod;
          }
        }

    return dp[0][0][k];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public int countPathsWithXorValue(int[][] grid, int k) {
    final int MOD = 1_000_000_007;
    final int MAX = 15;
    final int m = grid.length;
    final int n = grid[0].length;
    // dp[i][j][xors] := the number of paths from (i, j) to (m - 1, n - 1) with
    // XOR value `xors`
    int[][][] dp = new int[m][n][MAX + 1];

    dp[m - 1][n - 1][grid[m - 1][n - 1]] = 1;

    for (int i = m - 1; i >= 0; --i)
      for (int j = n - 1; j >= 0; --j)
        for (int xors = 0; xors <= MAX; ++xors) {
          if (i - 1 >= 0) {
            final int newXor = xors ^ grid[i - 1][j];
            dp[i - 1][j][newXor] += dp[i][j][xors];
            dp[i - 1][j][newXor] %= MOD;
          }
          if (j - 1 >= 0) {
            final int newXor = xors ^ grid[i][j - 1];
            dp[i][j - 1][newXor] += dp[i][j][xors];
            dp[i][j - 1][newXor] %= MOD;
          }
        }

    return dp[0][0][k];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def countPathsWithXorValue(self, grid, k):
    MOD = 1_000_000_007
    MAX = 15
    m = len(grid)
    n = len(grid[0])
    # dp[i][j][xors] := the number of paths from (i, j) to (m - 1, n - 1) with
    # XOR value `xors`
    dp = [[[0] * (MAX + 1)
          for _ in range(n)]
          for _ in range(m)]

    dp[-1][-1][grid[-1][-1]] = 1

    for i in reversed(range(m)):
      for j in reversed(range(n)):
        for xors in range(MAX + 1):
          if i - 1 >= 0:
            newXor = xors ^ grid[i - 1][j]
            dp[i - 1][j][newXor] += dp[i][j][xors]
            dp[i - 1][j][newXor] %= MOD
          if j - 1 >= 0:
            newXor = xors ^ grid[i][j - 1]
            dp[i][j - 1][newXor] += dp[i][j][xors]
            dp[i][j - 1][newXor] %= MOD

    return dp[0][0][k]

Approach 3: Bottom-up (forward)

  • Time: $O(16mn) = O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
    constexpr int kMod = 1'000'000'007;
    constexpr int kMax = 15;
    const int m = grid.size();
    const int n = grid[0].size();
    // dp[i][j][xors] := the number of paths from (0, 0) to (i, j) with XOR
    // value `xors`
    vector<vector<vector<int>>> dp(
        m, vector<vector<int>>(n, vector<int>(kMax + 1)));

    dp[0][0][grid[0][0]] = 1;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        for (int xors = 0; xors <= kMax; ++xors) {
          if (i + 1 < m) {
            const int newXor = xors ^ grid[i + 1][j];
            dp[i + 1][j][newXor] += dp[i][j][xors];
            dp[i + 1][j][newXor] %= kMod;
          }
          if (j + 1 < n) {
            const int newXor = xors ^ grid[i][j + 1];
            dp[i][j + 1][newXor] += dp[i][j][xors];
            dp[i][j + 1][newXor] %= kMod;
          }
        }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public int countPathsWithXorValue(int[][] grid, int k) {
    final int MOD = 1_000_000_007;
    final int MAX = 15;
    final int m = grid.length;
    final int n = grid[0].length;
    // dp[i][j][xors] := the number of paths from (0, 0) to (i, j) with XOR
    // value `xors`
    int[][][] dp = new int[m][n][MAX + 1];

    dp[0][0][grid[0][0]] = 1;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        for (int xors = 0; xors <= MAX; ++xors) {
          if (i + 1 < m) {
            final int newXor = xors ^ grid[i + 1][j];
            dp[i + 1][j][newXor] += dp[i][j][xors];
            dp[i + 1][j][newXor] %= MOD;
          }
          if (j + 1 < n) {
            final int newXor = xors ^ grid[i][j + 1];
            dp[i][j + 1][newXor] += dp[i][j][xors];
            dp[i][j + 1][newXor] %= MOD;
          }
        }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def countPathsWithXorValue(self, grid, k):
    MOD = 1_000_000_007
    MAX = 15
    m = len(grid)
    n = len(grid[0])
    # dp[i][j][xors] := the number of paths from (0, 0) to (i, j) with XOR
    # value `xors`
    dp = [[[0] * (MAX + 1)
          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 xors in range(MAX + 1):
          if i + 1 < m:
            newXor = xors ^ grid[i + 1][j]
            dp[i + 1][j][newXor] += dp[i][j][xors]
            dp[i + 1][j][newXor] %= MOD
          if j + 1 < n:
            newXor = xors ^ grid[i][j + 1]
            dp[i][j + 1][newXor] += dp[i][j][xors]
            dp[i][j + 1][newXor] %= MOD

    return dp[-1][-1][k]