LeetCode 解題筆記：3882. Minimum XOR Path in a Grid

作者：王一哲
日期：2026年10月28日


LeetCode 題目連結：3882. Minimum XOR Path in a Grid

解題想法

中等難度題。題目給一個 $m$ 列、$n$ 欄的陣列 $grid$，範圍為 $1 \leq m, n \leq 1000, ~ m \times n \leq 1000, ~ 0 \leq grid[i][j] \leq 1023$。出發點為左上角 $(0, 0)$，終點為右下角 $(m-1, n-1)$，只能向右或向下走，找出路徑上所有格子取 XOR 的最小值。

這題考動態規畫，可以建一個 2 維陣列 $dp$，$dp[i][j]$ 代表走到 $grid[i][j]$ 可能的路徑 XOR 值。因為取 XOR 的結果不可能大於原來的值，因此答案只在 $0$ 到 $1023$ 之間，Python 可以用 set 或是 bitmask 記錄可能的值，C++ 則可以用 bitset。由於更新 $dp$ 時只需要用到前一列的狀態，可以只開長度為 $n$ 的一維陣列記錄狀態，更新走到 $grid[i][j]$ 的狀態時，再建一個 bitset $nxt$ 記錄新的狀態，舊的狀態記錄在 $pre$，更新完 $nxt$ 之後再將資料存到 $dp[j]$。更新完所有的格子之後，答案在 $dp[n-1]$ 之中為 true 的最低位數。

Python 程式碼

bitmask，比想像中慢。Runtime: 3313 ms, beats 31.67%. Memory: 19.29 MB, beats 100.00%.

class Solution:
    def minCost(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # 0 ~ 1023，第 i 位為 1 代表存在加總為 i 的路徑
        dp = [0] * n
        
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:  # 起點
                    dp[0] = (1 << grid[0][0])
                else:  # 其它位置
                    pre = 0
                    if i > 0:  pre |= dp[j]  # 從上往下走
                    if j > 0:  pre |= dp[j-1]  # 從左往右走
                    
                    # 用 lowbit 從最後一個 1 往前更新
                    nxt = 0  # 新的狀態
                    val = grid[i][j]
                    while pre > 0:
                        lowbit = pre & -pre
                        k = lowbit.bit_length() - 1  # 第 k 位為 1
                        nxt |= (1 << (k ^ val))
                        pre &= pre - 1  # 清除最後的 1
                    
                        
                    dp[j] = nxt
                  
        # 在終點 n-1 由小到大找第 1 個 1 的位置 
        return (dp[n-1] & -dp[n-1]).bit_length() - 1

set. Runtime: 725 ms, beats 90.83%. Memory: 25.57 MB, beats 93.33%.

class Solution:
    def minCost(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # dp[j] 代表走到 grid[i][j] 可能的路徑 XOR 值
        dp = [set() for _ in range(n)]
        
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:  # 起點
                    dp[0].add(grid[0][0])
                else:  # 其它位置
                    pre = set()  # 前一個
                    if i > 0:  pre.update(dp[j])  # 從上往下走
                    if j > 0:  pre.update(dp[j-1])  # 從左往右走
                    
                    # 找可能的路徑 XOR 值
                    val = grid[i][j]
                    dp[j] = {x ^ val for x in pre}  # 新的狀態
                  
        # 在終點 n-1 找最小值
        return min(dp[n-1])

C++ 程式碼

Runtime: 74 ms, beats 98.76%. Memory: 40.43 MB, beats 92.98%.

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();  // m 列、n 欄
        // dp[j] 代表走到 grid[i][j] 可能的路徑 XOR 值，範圍為 0 ~ 1023
        // 如果 dp[j][k] = true，代表有值為 k 的路徑
        vector<bitset<1024>> dp (n);
        // 測試 i = 0 ~ m-1 列，試著走到 dp[j]
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                bitset<1024> nxt;  // 新的狀態
                if (i == 0 && j == 0) {  // 起點，grid[0][0]
                    nxt.set(grid[0][0]);
                } else {  // 一般狀況
                    bitset<1024> pre;  // 前一個狀態
                    if (i > 0) pre |= dp[j];  // 從上往下走
                    if (j > 0) pre |= dp[j-1];  // 從左往右走
                    int val = grid[i][j];
                    for(int k = 0; k < 1024; k++) {  // 更新可能的值
                        if (pre.test(k)) {  // 如果 pre[k] 為 true
                            nxt.set(k ^ val);  // nxt[k ^ val] 設定為 true
                        }
                    }
                }
                dp[j] = nxt;  // 更新 dp[j]
            }
        }
        // 於 dp[n-1] 之中，由小到大找第一個為 true 的 k 值
        for(int k = 0; k < 1024; k++) {
            if (dp[n-1].test(k)) {
                return k;
            }
        }
        return 0;  // 預設的回傳值
    }
};