3882. Minimum XOR Path in a Grid

/**
 * Problem: LeetCode 3882 - Minimum XOR Path in a Grid
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][][] dp = new boolean[m][n][1024];
        dp[0][0][grid[0][0]] = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                int val = grid[i][j];
                for (int x = 0; x < 1024; x++) {
                    boolean reachable = false;
                    if (i > 0 && dp[i - 1][j][x]) reachable = true;
                    if (j > 0 && dp[i][j - 1][x]) reachable = true;
                    if (reachable) dp[i][j][x ^ val] = true;
                }
            }
        }
        for (int x = 0; x < 1024; x++) {
            if (dp[m - 1][n - 1][x]) return x;
        }
        return -1;
    }
}

"""
Problem: LeetCode 3882 - Minimum XOR Path in a Grid
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        # dp[i][j][x] indicates whether XOR value x is reachable at cell (i, j)
        dp = [[[False] * 1024 for _ in range(n)] for _ in range(m)]
        dp[0][0][grid[0][0]] = True
        
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                val = grid[i][j]
                for x in range(1024):
                    reachable = False
                    if i > 0 and dp[i - 1][j][x]:
                        reachable = True
                    if j > 0 and dp[i][j - 1][x]:
                        reachable = True
                    if reachable:
                        dp[i][j][x ^ val] = True
                        
        for x in range(1024):
            if dp[m - 1][n - 1][x]:
                return x
                
        return -1

/**
 * Problem: LeetCode 3882 - Minimum XOR Path in a Grid
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<vector<bool>>> dp(m, vector<vector<bool>>(n, vector<bool>(1024, false)));
        
        dp[0][0][grid[0][0]] = true;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                int val = grid[i][j];
                for (int x = 0; x < 1024; x++) {
                    bool reachable = false;
                    if (i > 0 && dp[i - 1][j][x]) reachable = true;
                    if (j > 0 && dp[i][j - 1][x]) reachable = true;
                    if (reachable) {
                        dp[i][j][x ^ val] = true;
                    }
                }
            }
        }
        
        for (int x = 0; x < 1024; x++) {
            if (dp[m - 1][n - 1][x]) {
                return x;
            }
        }
        
        return -1;
    }
};

/**
 * Problem: LeetCode 3882 - Minimum XOR Path in a Grid
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
var minCost = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    // dp[i][j] stores reachable XOR states up to 1023
    const dp = Array.from({ length: m }, () =>
        Array.from({ length: n }, () => new Uint8Array(1024))
    );
    
    dp[0][0][grid[0][0]] = 1;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i === 0 && j === 0) continue;
            const val = grid[i][j];
            for (let x = 0; x < 1024; x++) {
                let reachable = false;
                if (i > 0 && dp[i - 1][j][x]) reachable = true;
                if (j > 0 && dp[i][j - 1][x]) reachable = true;
                if (reachable) {
                    dp[i][j][x ^ val] = 1;
                }
            }
        }
    }
    
    for (let x = 0; x < 1024; x++) {
        if (dp[m - 1][n - 1][x]) {
            return x;
        }
    }
    
    return -1;
};