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;
}