题目

3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。

给定一个由整数组成的row x col 的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？

注意：虽然幻方只能包含 1 到 9 的数字，但 grid 可以包含最多15的数字。

示例 1：

输入: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2] 输出: 1 解释: 下面的子矩阵是一个 3 x 3 的幻方：而这一个不是：总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。

示例 2:

输入: grid = [[8]] 输出: 0

提示:

row == grid.length
col == grid[i].length
1 <= row, col <= 10
0 <= grid[i][j] <= 15

解题思路

这是一个经典的暴力枚举（Brute Force）或模拟问题。

由于题目给定的数据规模非常小（$row, col \le 10$），我们完全可以遍历矩阵中每一个可能的 $3 \times 3$ 子矩阵，并逐一检查它是否符合“幻方”的定义。

我们需要明确 1-9 的 $3 \times 3$ 幻方的几个关键数学性质，这可以简化我们的判断逻辑：

数字范围：必须包含 1 到 9 的所有数字，且不重复（Distinct）。
幻和（Magic Sum）：1 到 9 的总和是 45。因为有 3 行，每行相等，所以每一行（列、对角线）的和必须是 $45 / 3 = 15$。
中心点：$3 \times 3$ 幻方的中心数字一定是 5。

第一步：边界检查

如果输入矩阵的行数或列数小于 3，根本无法形成 $3 \times 3$ 的子矩阵，直接返回 0。

第二步：遍历所有可能的左上角

我们遍历网格中所有可能的 $3 \times 3$ 子矩阵的左上角坐标 $(r, c)$。

$r$ 的范围是 $0$ 到 $row - 3$。
$c$ 的范围是 $0$ 到 $col - 3$。

第三步：检查子矩阵（check 函数）

对于每一个左上角 $(r, c)$ 确定的 $3 \times 3$ 区域，进行如下检查：

快速筛选：检查该子矩阵的中心元素 grid[r+1][c+1] 是否为 5。如果不是，直接排除（虽然这步不是必须的，但能加速）。
合法性与去重：
- 遍历这 9 个格子，确保每个数字都在 1-9 之间。
- 确保这 9 个数字互不相同（可以使用一个长度为 10 的布尔数组或哈希集合来记录）。
和的校验：
- 计算 3 行的和，看是否都等于 15。
- 计算 3 列的和，看是否都等于 15。
- 计算 2 条对角线的和，看是否都等于 15。

如果以上所有条件都满足，则计数器 +1。

具体代码

func numMagicSquaresInside(grid [][]int) int {
    row := len(grid)
    col := len(grid[0])
    if row < 3 || col < 3 {
        return 0
    }

    count := 0
    for i := 0; i <= row-3; i++ {
        for j := 0; j <= col-3; j++ {
            if isMagic(grid, i, j) {
                count++
            }
        }
    }
    return count
}

func isMagic(grid [][]int, r, c int) bool {
    // 剪枝 1：中心必须是 5
    if grid[r+1][c+1] != 5 {
        return false
    }

    // 剪枝 2：必须是 1~9 且不重复
    seen := make([]bool, 10)
    for i := r; i < r+3; i++ {
        for j := c; j < c+3; j++ {
            v := grid[i][j]
            if v < 1 || v > 9 || seen[v] {
                return false
            }
            seen[v] = true
        }
    }

    // 检查行
    for i := 0; i < 3; i++ {
        sum := 0
        for j := 0; j < 3; j++ {
            sum += grid[r+i][c+j]
        }
        if sum != 15 {
            return false
        }
    }

    // 检查列
    for j := 0; j < 3; j++ {
        sum := 0
        for i := 0; i < 3; i++ {
            sum += grid[r+i][c+j]
        }
        if sum != 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
}

beautifulremi / 840. 矩阵中的幻方

题目

解题思路

第一步：边界检查

第二步：遍历所有可能的左上角

第三步：检查子矩阵（check 函数）

具体代码