※ 引述 《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;
}
};
```