840. Magic Square In Grid

https://leetcode.com/problems/magic-squares-in-grid?envType=daily-question&envId=2025-12-30

這題是乍看之下有點難的 Medium，實際上在 Medium 難度中應該算中下（個人觀點）。

看到題目的當下，便直接浮現了暴力法破解：用一個 window 遍歷整個矩陣，每次都計算這個矩陣的所有 row, col, diag。但可想而知這一定非常慢！

因此下一秒我便開始思考優化這個暴力法。

首先看著範例矩陣，我腦袋中直接浮現了這個 3*3 的矩陣中心是不是一定要 5（直覺告訴我）。我覺得我的想法是對的，但在面試時我總不能真的這樣說吧哈哈哈，因此努力想了個證明。

首先 1+2+3+...+9 = 45，這是一個矩陣的總和。因此每個 row, col, diag 的和各為 15 (45/3)。觀察一下，發現矩陣中心總共會參與四條線，分別是兩條對角線與一條正中橫線與直線。也就是必須要有四組數字可以跟矩陣中心相加後和為 15。如果中心是 5，剛好會有： (6,4), (7,3), (8,2), (9,1) 這四個相加為 15 的組合。但若是中心非 5，假設 6 好了，那便只會有：(5, 4), (7, 2), (8, 1)這三種組合。到這邊可以試試看其他組合，除了 5 之外皆沒有可以滿足中心要有四種搭配組合的條件！因此中心必為 5。

同樣證明，角落的四個數字需要有三種組合，推導後會發現只有 2, 4, 6, 8 滿足，因此角落必為這四個偶數！其他數字就是剩下的，沒啥好說。

那來看一下我的 code 吧！

class Solution {

private:

public:
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        // center 一定要是 5(只有 5 可以湊出四種相加為 15 的組合)
        // 角落只能 4, 8, 2, 6
        // 其他
        int m = grid[0].size();
        int n = grid.size();
        int ans = 0;
    
        for(int i = 0; i+2 < m; i++) {
            for(int j = 0; j+2 < n; j++) {
                if (! checkCenter(grid[j+1][i+1])) continue;
                if (! checkCorner(j, i, grid)) continue;
                if (! checkOther(j, i, grid)) continue;

                ans++;
            }
        }

        return ans;
        
    }
    
    bool checkCenter(int& center) {
        return (center == 5);
    }

    bool checkCorner(int& x, int& y, vector<vector<int>>& gridCopy) {

        if(gridCopy[x][y] + gridCopy[x+2][y+2] != 10) return false;
        if(gridCopy[x][y+2] + gridCopy[x+2][y] != 10) return false;
        
        if(gridCopy[x][y] % 2) return false;
        if(gridCopy[x+2][y] % 2) return false;
        if(gridCopy[x+2][y+2] % 2) return false;
        if(gridCopy[x][y+2] % 2) return false;

        return true;
    }

    bool checkOther(int& x, int& y, vector<vector<int>>& gridCopy) {
        if(15 - gridCopy[x][y] - gridCopy[x+1][y] - gridCopy[x+2][y]) return false;
        if(15 - gridCopy[x][y] - gridCopy[x][y+1] - gridCopy[x][y+2]) return false;
        if(15 - gridCopy[x+2][y] - gridCopy[x+2][y+1] - gridCopy[x+2][y+2]) return false;
        if(15 - gridCopy[x][y+2] - gridCopy[x+1][y+2] - gridCopy[x+2][y+2]) return false;
        return true;
    }
};

我的程式碼可以說是非常直觀，本質上還是暴力破解了，只是讓每個 window 計算的過程中可以 follow 我上面說的數學特點來加速。

蠻意外的是竟然這樣可以 beat 100% runtime。因為我 code 寫得很累贅，還以為 runtime 成績不好。memory 的成績只有 beat 67%，有空的話會在 Best Solution 裡分享我找到的 memory 使用優化。

Best Solution