840. Magic Squares In Grid
直接暴力解看看
https://i.imgur.com/YuyKUCe.png
class Solution {
public:
int numMagicSquaresInside(vector<vector<int>>& grid) {
if (grid.size() < 3 || grid[0].size() < 3) {
return 0;
}
int result = 0;
for (size_t x = 0; x < grid.size() - 2; x++) {
for (size_t y = 0; y < grid[x].size() - 2; y++) {
result += isSubGridMagic(grid, x, y);
}
}
return result;
}
private:
static bool isSubGridMagic(const vector<vector<int>>& grid, size_t xStart,
size_t yStart) {
vector<bool> distinct(9, false);
for (size_t x = xStart; x < xStart + 3; x++) {
for (size_t y = yStart; y < yStart + 3; y++) {
int distinctIndex = grid[x][y] - 1;
if (0 <= distinctIndex && distinctIndex <= 8) {
distinct[distinctIndex] = true;
}
}
}
constexpr int MAGIC_SUM = 15;
return all_of(distinct.cbegin(), distinct.cend(),
[](bool tf) { return tf == true; }) &&
grid[xStart + 0][yStart + 0] + grid[xStart + 0][yStart + 1] +
grid[xStart + 0][yStart + 2] ==
MAGIC_SUM &&
grid[xStart + 1][yStart + 0] + grid[xStart + 1][yStart + 1] +
grid[xStart + 1][yStart + 2] ==
MAGIC_SUM &&
grid[xStart + 2][yStart + 0] + grid[xStart + 2][yStart + 1] +
grid[xStart + 2][yStart + 2] ==
MAGIC_SUM &&
grid[xStart + 0][yStart + 0] + grid[xStart + 1][yStart + 0] +
grid[xStart + 2][yStart + 0] ==
MAGIC_SUM &&
grid[xStart + 0][yStart + 1] + grid[xStart + 1][yStart + 1] +
grid[xStart + 2][yStart + 1] ==
MAGIC_SUM &&
grid[xStart + 0][yStart + 2] + grid[xStart + 1][yStart + 2] +
grid[xStart + 2][yStart + 2] ==
MAGIC_SUM &&
grid[xStart + 0][yStart + 0] + grid[xStart + 1][yStart + 1] +
grid[xStart + 2][yStart + 2] ==
MAGIC_SUM &&
grid[xStart + 2][yStart + 0] + grid[xStart + 1][yStart + 1] +
grid[xStart + 0][yStart + 2] ==
MAGIC_SUM;
}
};