Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

※ 引述 《enmeitiryous (enmeitiryous)》 之銘言：
: 　
: 840. Magic Squares In Grid
: 題目:
: 給你一個matrix grid:其中0<=grid[i][j]<=15，求grid中有多少個3*3submatrix符合
: magic square的定義
: 　
: 思路:
: 有興趣可以看一下magic sqaure的維基，可以知道不論怎麼填3*3的magic square的中心
: 值一定會是5，且row sum必是15，就按照magic square的定義寫一個額外func來確定給定
: 的方陣是不是magic square，且只在遍歷原matrix時遇到不在邊界上的5才進行檢查。
: 結果比暴力法遍歷慢 唉
:  


思路:

暴力暴力暴力暴力
多寫一個函式跑判定
用紀錄的
如果這個matrix大一點
搞不好就要在原本grid裡面用到prefix sum?
姆咪

```cpp
class Solution {
public:

    bool ok(vector<vector<int>>& grid , int i , int j)
    {
        vector<int> num(16,0);
        vector<int> rs(3,0);
        vector<int> cs(3,0);
        for(int k = i-1 ; k <= i+1 ; k ++)
        {

            for(int p = j-1 ; p <= j+1 ; p ++)
            {
                num[grid[k][p]]++;
                rs[k+1-i]+=grid[k][p];
                cs[p+1-j]+=grid[k][p];
            }
        }
        for(int p = 1 ; p <= 9 ; p ++)
        {
            if(!num[p])return false;
        }
        for(int p = 0 ; p < 2; p ++)
        {
            if(rs[p]!=rs[p+1])return false;
            if(cs[p]!=cs[p+1])return false;
        }
        if(cs[0]!=rs[0])return false;
        if(grid[i-1][j-1] + grid[i+1][j+1] != grid[i+1][j-1]+grid[i-1][j+1])retu
rn false;
        return true;
    }

    int numMagicSquaresInside(vector<vector<int>>& grid)
    {
        int res = 0;
        int n = grid.size();
        int m = grid[0].size();

        for(int i = 1 ; i < n-1 ; i ++)
        {
            for(int j = 1 ; j < m-1 ; j ++)
            {
                if(ok(grid,i,j))res++;
            }
        }

        return res;


    }
};
```




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.12.220 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723169414.A.81B.html
→ SydLrio: 你有什麼用
推 mrsonic: 這麼早發有什麼用