2024-08-09
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 a row x col grid of integers, how many 3 x 3 contiguous magic square
subgrids are there?
Note: while a magic square can only contain numbers from 1 to 9, grid may
contain numbers up to 15
我只会暴力解
丑死
可是跑起来好快
Compiler做了什么事
class Solution {
public:
int numMagicSquaresInside(vector<vector<int>>& grid) {
if (grid.size() < 3 || grid[0].size() < 3) {
return 0;
}
int count = 0;
for (int r = 1; r < grid.size() - 1; ++r) {
for (int c = 1; c < grid[0].size() - 1; ++c) {
if (isMagic(r, c, grid)) {
count++;
}
}
}
return count;
}
private:
bool isMagic(int r, int c, vector<vector<int>>& grid) {
if (5 != grid[r][c]) {
return false;
}
if (15 != grid[r-1][c-1] + grid[r-1][c] + grid[r-1][c+1]) {
return false;
}
if (10 != grid[r][c-1] + grid[r][c+1]) {
return false;
}
if (15 != grid[r+1][c-1] + grid[r+1][c] + grid[r+1][c+1]) {
return false;
}
if (15 != grid[r-1][c-1] + grid[r][c-1] + grid[r+1][c-1]) {
return false;
}
if (10 != grid[r-1][c] + grid[r+1][c]) {
return false;
}
if (15 != grid[r-1][c+1] + grid[r][c+1] + grid[r+1][c+1]) {
return false;
}
if (10 != grid[r-1][c-1] + grid[r+1][c+1]) {
return false;
}
if (10 != grid[r-1][c+1] + grid[r+1][c-1]) {
return false;
}
vector<int> counter(10);
for (int i = -1; i <= 1; ++i) {
for (int j = -1; j <= 1; ++j) {
if (grid[r+i][c+j] > 9) {
return false;
}
if (counter[grid[r+i][c+j]]) {
return false;
}
counter[grid[r+i][c+j]]++;
}
}
return true;
}
};