※ 引述《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才进行检查。
: : 结果比暴力法遍历慢 唉
思路 暴力法 走过每一个3x3左上点
先写一个func检查中心==5, 每格是不是数值在1-9
再写一个func检查row sum, col sum, diagonal sum == 15
都是就把答案+1
class Solution {
public:
int isNumsValid(vector<vector<int>>& grid, int i, int j){
vector<int> valid(9);
if(grid[i+1][j+1] != 5) return false;
for(int r = 0; r < 3; ++r){
for(int c = 0; c < 3; ++c){
int n = grid[i+r][j+c];
if ( n == 0 || n > 9) return false;
valid[n-1]++;
}
}
for(auto& v: valid){
if(v > 1 || v == 0) return false;
}
return true;
}
int isSumValid(vector<vector<int>>& grid, int i, int j){
int row_sum[3]{0}, col_sum[3]{0};
for(int r = 0; r < 3; ++r){
for(int c = 0; c < 3; ++c){
row_sum[r] += grid[i+r][j+c];
col_sum[c] += grid[i+r][j+c];
}
}
for(int i = 0; i < 3; ++c){
if(row_sum[i] !=15 || col_sum[i] != 15) return false;
}
int diagonal_sum = grid[i][j] + grid[i+1][j+1] + grid[i+2][j+2];
int diagonal_sum2 = grid[i][j+2] + grid[i+1][j+1] + grid[i+2][j];
return diagonal_sum == diagonal_sum2;
}
int numMagicSquaresInside(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), ans = 0;
if(m < 3 || n < 3) return 0;
for(int i = 0; i < m-2;++i){
for(int j = 0; j < n-2;++j){
if(!isNumsValid(grid, i, j)) continue;
if(!isSumValid(grid, i, j)) continue;
ans++;
}
}
return ans;
}
};

ㄉㄕ

ㄉㄕ