# 840. Magic Squares In Grid

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an `grid` of integers, how many 3 x 3 “magic square” subgrids are there?  (Each subgrid is contiguous).

Example 1:

``````Input: [[4,3,8,4],
[9,5,1,9],
[2,7,6,2]]
Output: 1
Explanation:
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.
``````

Note:

1. `1 <= grid.length <= 10`
2. `1 <= grid[0].length <= 10`
3. `0 <= grid[i][j] <= 15`

``````class Solution {
public:
int numMagicSquaresInside(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), res = 0;
for (int i = 0; i < m - 2; ++i) {
for (int j = 0; j < n - 2; ++j) {
if (grid[i + 1][j + 1] == 5 && isValid(grid, i, j)) ++res;
}
}
return res;
}
bool isValid(vector<vector<int>>& grid, int i, int j) {
vector<int> cnt(10);
for (int x = i; x < i + 2; ++x) {
for (int y = j; y < j + 2; ++y) {
int k = grid[x][y];
if (k < 1 || k > 9 || cnt[k] == 1) return false;
cnt[k] = 1;
}
}
if (15 != grid[i][j] + grid[i][j + 1] + grid[i][j + 2]) return false;
if (15 != grid[i + 1][j] + grid[i + 1][j + 1] + grid[i + 1][j + 2]) return false;
if (15 != grid[i + 2][j] + grid[i + 2][j + 1] + grid[i + 2][j + 2]) return false;
if (15 != grid[i][j] + grid[i + 1][j] + grid[i + 2][j]) return false;
if (15 != grid[i][j + 1] + grid[i + 1][j + 1] + grid[i + 2][j + 1]) return false;
if (15 != grid[i][j + 2] + grid[i + 1][j + 2] + grid[i + 2][j + 2]) return false;
if (15 != grid[i][j] + grid[i + 1][j + 1] + grid[i + 2][j + 2]) return false;
if (15 != grid[i + 2][j] + grid[i + 1][j + 1] + grid[i][j + 2]) return false;
return true;
}
};
``````

https://leetcode.com/problems/magic-squares-in-grid/

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation