Minimum xor path in a grid

38.9% acceptance

Mar 31, 2026

You are given a 2D integer array grid of size m * n. You start at the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1). At each step, you may move either right or down. The cost of a path is defined as the bitwise XOR of all the values in the cells along that path, including the start and end cells. Return the minimum possible XOR value among all valid paths from (0, 0) to (m - 1, n - 1).

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    // Values up to 1023 (10 bits). Use DP with bitmask optimization.
    // dp[i][j] = set of possible XOR values reaching (i,j).
    // Since values are 0..1023, XOR values are 0..1023.
    // We can use bitset: dp[i][j] is a u128 or similar? 1024 bits.
    // m*n <= 1000, so feasible.
    // Actually, use a vec of bool or a bitset.
    
    let max_xor = 1024;
    let mut dp = vec![vec![vec![false; max_xor]; n]; m];
    dp[0][0][grid[0][0] as usize] = true;
    
    for i in 0..m {
      for j in 0..n {
        if i == 0 && j == 0 {
          continue;
        }
        let v = grid[i][j] as usize;
        // From top
        if i > 0 {
          for x in 0..max_xor {
            if dp[i - 1][j][x] {
              dp[i][j][x ^ v] = true;
            }
          }
        }
        // From left
        if j > 0 {
          for x in 0..max_xor {
            if dp[i][j - 1][x] {
              dp[i][j][x ^ v] = true;
            }
          }
        }
      }
    }
    
    for x in 0..max_xor {
      if dp[m - 1][n - 1][x] {
        return x as i32;
      }
    }
    -1
  }
}