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才進行檢查。
結果比暴力法遍歷慢 唉
bool he_pler(vector<vector<int>> &grid, int i, int j){
unordered_set<int> gg;
for(int y=i-1;y<i+2;++y){
for(int x=j-1;x<j+2;++x){
if(grid[y][x]>9 || grid[y][x]<1){
return false;
}
gg.insert(grid[y][x]);
}
}
if(gg.size()<9){
return false;
}
if(grid[i][j]+grid[i][j+1]+grid[i][j-1]!=15){
return false;
}
if(grid[i+1][j]+grid[i+1][j+1]+grid[i+1][j-1]!=15){
return false;
}
if(grid[i-1][j]+grid[i-1][j+1]+grid[i-1][j-1]!=15){
return false;
}
if(grid[i+1][j]+grid[i][j]+grid[i-1][j]!=15){
return false;
}
if(grid[i+1][j-1]+grid[i][j-1]+grid[i-1][j-1]!=15){
return false;
}
if(grid[i+1][j+1]+grid[i][j+1]+grid[i-1][j+1]!=15){
return false;
}
if(grid[i-1][j-1]+grid[i][j]+grid[i+1][j+1]!=15){
return false;
}
if(grid[i-1][j+1]+grid[i][j]+grid[i+1][j-1]!=15){
return false;
}
return true;
}
int numMagicSquaresInside(vector<vector<int>>& grid) {
if(grid.size()<3 || grid[0].size()<3){
return 0;
}
int m=grid.size();
int n=grid[0].size();
int ans=0;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(grid[i][j]==5 &&i>0 &&i<m-1 && j>0 && j<n-1){
if(he_pler(grid,i,j)){
ans++;
}
}
}
}
return ans;
}