📘 題目敘述
給定一個 m × n 的整數矩陣 grid。
你從左上角 (0, 0) 出發，目標是走到右下角 (m - 1, n - 1)。
每一步只能：
- 往右走
- 往下走
一條路徑的 cost 定義為：
- 路徑上所有格子的數值做 bitwise XOR
- 包含起點和終點
請回傳所有合法路徑中，最小 possible XOR value。
條件限制
1 <= m == grid.length <= 10001 <= n == grid[i].length <= 1000m * n <= 10000 <= grid[i][j] <= 1023
🧠 解題思路
我這題的想法是用 DP。
因為每個位置 (i, j) 都只能從：
- 上面
(i - 1, j) - 左邊
(i, j - 1)
走過來，所以我可以把問題想成：
走到某個格子時，所有可能出現的 XOR 值有哪些？
只要我知道前一格所有可能的 XOR 值，就能把目前格子的值 grid[i][j] 再 XOR 上去，得到走到這一格的新結果。
所以我這份寫法用一個二維 DP，裡面的每一格都放一個 unordered_set<int>，用來記錄：
- 走到這個位置時
- 所有可能出現的 XOR 結果
最後我只要看右下角那格的 set，把裡面最小的值找出來，就是答案。
所有變數
m：矩陣列數n：矩陣行數dp：二維 DP，每個dp[i][j]都是一個unordered_set<int>，記錄走到(i, j)時所有可能的 XOR 值ans：最後答案，記錄右下角所有可能 XOR 值中的最小值
🪜 主要流程步驟
1. 先建立 DP 狀態
我先建立 unordered_set 的 vector 這表示 dp[i][j] 不是一個單一數值，而是一整個集合。
因為這題不是一般那種「走到這格的最小值」就夠了。 同一個位置可能會被不同路徑走到，而且不同路徑會產生不同的 XOR 結果，所以我不能只保留一個值，而是要把所有可能的 XOR 值都存下來。
2. 初始化起點
起點 (0, 0) 只有一種走法，就是一開始站在那裡。 所以走到起點的 XOR 值也只有一個，就是 grid[0][0] 本身。
所以我先做：
dp[0][0].insert(grid[0][0]);
這樣後面的轉移就可以從這個初始狀態開始擴展。
3. 逐格做 DP 轉移
我用兩層迴圈把整個矩陣掃過一次。 對每個位置 (i, j)，如果不是起點，就去看它能不能從上面或左邊走過來。
如果可以從上面走過來，也就是 i > 0，那我就把 dp[i - 1][j] 裡面的每個 XOR 值都拿出來，和目前格子的值做 XOR，然後放進 dp[i][j]。
程式裡這段：
if (i > 0) {
for (int x : dp[i - 1][j]) {
dp[i][j].insert(x ^ grid[i][j]);
}
}
意思就是：
x是某條路徑走到上方格子時的 XOR 值- 如果現在再走一步到
(i, j)，那新的 XOR 值就會變成x ^ grid[i][j]
如果可以從左邊走過來，也就是 j > 0，做法完全一樣：
也就是把左邊所有可能的 XOR 值延伸到目前這格。
這樣每一格最後存的，就是所有能走到那裡的路徑所產生的 XOR 結果。
4. 為什麼這裡用 unordered_set
我這題直接用 unordered_set<int> 來存每格所有可能的 XOR 值。
原因是：
- 同一個位置可能由很多不同路徑走到
- 但不同路徑有時候會算出一樣的 XOR 值
- 如果我全部都存下來，會有很多重複資料
所以用 set 的好處是：
- 自動去重
- 只保留「不同的 XOR 結果」
- 後面轉移時也比較乾淨
而且這題的 grid[i][j] <= 1023，數值範圍不大，XOR 的可能結果數量也不會無限制爆掉，所以這種寫法是可行的。
5. 最後從右下角找最小值
當整個 DP 都做完之後，dp[m - 1][n - 1] 裡面就放著：
- 所有從左上走到右下的合法路徑
- 對應可能得到的所有 XOR 值
所以我最後只要把這個 set 掃過一次，找最小值就好：
最後回傳 ans，就是答案。
⏱️ 複雜度
設每個 dp[i][j] 中最多有 S 種不同的 XOR 值。
- 時間複雜度：
O(mnS)
每個格子都要從上方和左方的 set 做轉移，每次轉移要枚舉裡面的 XOR 值。
- 空間複雜度：
O(mnS)
因為每個格子都存一個 set，裡面放這格所有可能的 XOR 值。
💻 程式碼實作
class Solution {
public:
int minCost(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<unordered_set<int>>> dp(m, vector<unordered_set<int>>(n));
dp[0][0].insert(grid[0][0]);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) continue;
if (i > 0) {
for (int x : dp[i - 1][j]) {
dp[i][j].insert(x ^ grid[i][j]);
}
}
if (j > 0) {
for (int x : dp[i][j - 1]) {
dp[i][j].insert(x ^ grid[i][j]);
}
}
}
}
int ans = INT_MAX;
for (int x : dp[m - 1][n - 1]) {
ans = min(ans, x);
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/contest/biweekly-contest-179/problems/minimum-xor-path-in-a-grid/