1. 理解 3×3 幻方的核心性质
要判断一个 3×3 的矩阵是否为幻方，必须同时满足以下几个严格条件：
- 数字构成：必须包含 1 到 9 的所有数字，且 不重复。
- 和相等：每一行、每一列、两条对角线的和必须相等。
数学推导（关键点）：
- 1 到 9 的总和是 45。
- 因为有 3 行，且每行和相等，所以每一行的和必须是 45 / 3 = 15。
- 因此，幻方常数（每行/列/对角线之和）必须固定为 15。
- 中心点性质：通过数学推导（四条穿过中心的线的和 – 3倍中心值 = 总和），可以得出 3×3 幻方的 中心元素必须是 5。
- 这是一个非常有用的快速筛选条件：如果一个 3×3 子矩阵的中心不是 5，它一定不是幻方。
2. 解题算法流程
我们可以采用 滑动窗口 或 枚举左上角 的方式来遍历整个 grid。
步骤如下：
- 边界检查：
- 如果
grid的行数或列数小于 3，直接返回 0（无法构成 3×3 矩阵）。
- 如果
- 遍历所有可能的 3×3 子矩阵：
- 设
R为行数，C为列数。 - 我们需要枚举子矩阵的左上角坐标 (i, j)。
- i 的范围是从 0 到 R – 3。
- j 的范围是从 0 到 C – 3。
- 设
- 对每个子矩阵进行验证：对于以 (i, j) 为左上角的 3×3 区域，执行以下检查：
- 快速检查：看中心元素
grid[i+1][j+1]是否为 5。如果不是，直接跳过。 - 范围与去重检查：
- 遍历该 3×3 区域的 9 个数字。
- 确保每个数字都在
1-9之间。 - 确保没有重复数字（可以使用一个布尔数组或哈希集合来记录）。
- 和的检查：
- 计算 3 行的和，看是否都等于 15。
- 计算 3 列的和，看是否都等于 15。
- 计算 2 条对角线的和，看是否都等于 15。
- (注：如果数字 1-9 不重复且中心为 5，其实只要检查行和列即可，但为了逻辑严谨，全检查也不会超时)。
- 快速检查：看中心元素
- 计数：
- 如果上述所有条件都满足，计数器 +1。
3. 代码实现示例 (C++)
#include <vector>
#include <numeric>
using namespace std;
class Solution {
public:
int numMagicSquaresInside(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
if (rows < 3 || cols < 3) return 0;
int count = 0;
// 遍历所有可能的 3x3 子矩阵左上角 (i, j)
for (int i = 0; i <= rows - 3; ++i) {
for (int j = 0; j <= cols - 3; ++j) {
if (isMagic(grid, i, j)) {
count++;
}
}
}
return count;
}
private:
bool isMagic(const vector<vector<int>>& grid, int r, int c) {
// 1. 快速检查：3x3 幻方的中心元素必须是 5
if (grid[r + 1][c + 1] != 5) return false;
// 2. 检查数字是否在 1-9 之间且不重复
// 使用一个简单的频次数组（或位运算）来记录
int count[16] = {0};
for (int i = r; i < r + 3; ++i) {
for (int j = c; j < c + 3; ++j) {
int val = grid[i][j];
// 如果数字不在 1-9 范围内，或者出现重复，则不是幻方
if (val < 1 || val > 9 || ++count[val] > 1) {
return false;
}
}
}
//
// 3. 检查行、列、对角线之和是否均为 15
// 检查行和
if (grid[r][c] + grid[r][c+1] + grid[r][c+2] != 15) return false;
if (grid[r+1][c] + grid[r+1][c+1] + grid[r+1][c+2] != 15) return false;
if (grid[r+2][c] + grid[r+2][c+1] + grid[r+2][c+2] != 15) return false;
// 检查列和
if (grid[r][c] + grid[r+1][c] + grid[r+2][c] != 15) return false;
if (grid[r][c+1] + grid[r+1][c+1] + grid[r+2][c+1] != 15) return false;
if (grid[r][c+2] + grid[r+1][c+2] + grid[r+2][c+2] != 15) return false;
// 检查两条对角线和
if (grid[r][c] + grid[r+1][c+1] + grid[r+2][c+2] != 15) return false;
if (grid[r][c+2] + grid[r+1][c+1] + grid[r+2][c] != 15) return false;
return true;
}
};
4. 复杂度分析
- 时间复杂度：O(R \times C)。
- 我们需要遍历网格中的每个单元格作为潜在的左上角。
- 对于每个位置，我们只检查固定的 9 个格子（常数时间操作）。
- 因为 R, C \le 10，计算量非常小。
- 空间复杂度：O(1)。
- 只使用了常数级别的额外空间来存储临时变量。