1738. Find Kth Largest XOR Coordinate Value

這題的精髓在於怎麼建立dp的表

我們會分成4類

1. i == 0, j == 0 
   只有自己xor自己, 肯定還是等於自己
2. i == 0, j!= 0
   只需要xor 左邊的值
   dp[i][j] = dp[i][j-1] ^ matrix[i][j]
3. i != 0, j == 0
   只需要xor上邊的值
   dp[i][j] = dp[i - 1][j] ^ matrix[i][j]
4. i != 0, j!= 0
    dp[i][j] = dp[i -1][j - 1] ^  dp[i][j-1] ^ dp[i-1][j] ^  matrix[i][j];
   這個條件需要想一下, 下面解釋

針對上面第四個條件, 我們舉一個例子

matrix = [[5,2],[1,6]], k = 1

當(1, 1)時, 如果我們要做就是 5 xor 2 xor 1 xor 6

可我們的(1, 0), (0, 1)分別為 5 xor 2, 5 xor 1

若我們在建立表, 用到這兩個

5 xor 2 xor 5 xor 1, 5會被消滅,

所以我們得在xor原本的5一次(i-1, j-1), 這就是上方一次xor 三個選項的由來

最終才能

5 xor 2 xor 1 xor 6

最後我們順便將每個值加到一個陣列裡, 排列後回傳第k大的值

class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));
        vector<int> rank;
        for(int i = 0; i < matrix.size();i++){
            for(int j = 0; j < matrix[0].size(); j++){
                if(j == 0 && i == 0){
                   dp[i][j] = matrix[i][j];
                }else if(j == 0){
                    dp[i][j] = dp[i-1][j] ^ matrix[i][j];
                }else if(i== 0){
                    dp[i][j] = dp[i][j-1] ^ matrix[i][j];
                }else{
                    dp[i][j] = dp[i -1][j - 1] ^  dp[i][j-1] ^ dp[i-1][j] ^  matrix[i][j];
                }
                rank.push_back(dp[i][j]);
                
            }
        }
        sort(rank.begin(), rank.end());
        
        return rank.at(rank.size() - k);
    }
};