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

ㄉㄕ

ㄉㄕ