0840. 矩阵中的幻方【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 枚举

1. 📝 题目描述

• leetcode

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

2. 🎯 s.1 - 枚举

c

bool isMagic(int** grid, int r, int c) {
    bool seen[10] = {false};
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) {
            int v = grid[r+i][c+j];
            if (v < 1 || v > 9 || seen[v]) return false;
            seen[v] = true;
        }
    for (int i = 0; i < 3; i++) {
        if (grid[r+i][c] + grid[r+i][c+1] + grid[r+i][c+2] != 15) return false;
        if (grid[r][c+i] + grid[r+1][c+i] + grid[r+2][c+i] != 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;
}

int numMagicSquaresInside(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0], res = 0;
    for (int i = 0; i <= m - 3; i++)
        for (int j = 0; j <= n - 3; j++)
            if (isMagic(grid, i, j)) res++;
    return res;
}

js

/**
 * @param {number[][]} grid
 * @return {number}
 */
var numMagicSquaresInside = function (grid) {
  const m = grid.length,
    n = grid[0].length
  let res = 0
  for (let i = 0; i <= m - 3; i++)
    for (let j = 0; j <= n - 3; j++) if (isMagic(grid, i, j)) res++
  return res
}

function isMagic(grid, r, c) {
  const seen = new Array(10).fill(false)
  for (let i = 0; i < 3; i++)
    for (let j = 0; j < 3; j++) {
      const v = grid[r + i][c + j]
      if (v < 1 || v > 9 || seen[v]) return false
      seen[v] = true
    }
  for (let i = 0; i < 3; i++) {
    if (grid[r + i][c] + grid[r + i][c + 1] + grid[r + i][c + 2] !== 15)
      return false
    if (grid[r][c + i] + grid[r + 1][c + i] + grid[r + 2][c + i] !== 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
}

py

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        def is_magic(r: int, c: int) -> bool:
            vals = [grid[r+i][c+j] for i in range(3) for j in range(3)]
            if sorted(vals) != list(range(1, 10)): return False
            for i in range(3):
                if sum(grid[r+i][c:c+3]) != 15: return False
                if grid[r][c+i] + grid[r+1][c+i] + grid[r+2][c+i] != 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
        m, n = len(grid), len(grid[0])
        return sum(1 for i in range(m-2) for j in range(n-2) if is_magic(i, j))

• 时间复杂度：$O(m\times n)$，其中 m 和 n 是矩阵的行列数
• 空间复杂度：$O(1)$

算法思路：

• 枚举每个 $3\times 3$ 子矩阵，检查是否包含 1-9 且行、列、对角线和均为 15