题目
难度：★★☆☆☆
类型：几何
3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。
给定一个由整数组成的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。
提示
1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15
示例
输入: [[4,3,8,4],
[9,5,1,9],
[2,7,6,2]]
输出: 1
解释:
下面的子矩阵是一个 3 x 3 的幻方：
438
951
276
而这一个不是：
384
519
762
总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
解答
3*3幻方的条件：
所有元素均在1到9之间，且各不相同；
每一行，每一列及两个对角线上的元素和相等。
注意到题目中矩阵的大小不超过100个数字，因此我们可以使用暴力求解的方法：
遍历矩阵中所有的3*3方格，分别判断是否满足幻方的条件。
这里，我们定义了函数（get_quare）提取矩阵中指定的方格，定义函数（is_magic_square）判断方格是否是幻方。
class Solution(object):
def numMagicSquaresInside(self, grid):
# 获得指定区域内的所有元素。
def get_square(grid, left, top, right, bottom):
res = []
for r in range(top, bottom):
row = []
for c in range(left, right):
row.append(grid[r][c])
res.append(row)
return res
def is_magic_square(square):
sums = [] # 用于保存每一行，每一列以及对角线元素的和
r, c = len(square), len(square[0]) # 幻方的长宽
sums.extend([sum(row) for row in square]) # 考察每一行的和
sums.extend([sum(column) for column in zip(*square)]) # 考察每一列的和
sums.append(sum([square[i][i] for i in range(min(r, c))])) # 对角线1的和
sums.append(sum([square[-i-1][i] for i in range(min(r, c))])) # 对角线2的和
nums = [square[i][j] for i in range(r) for j in range(c)] # 用于保存所有元素的列表
# 幻方条件：所有行、列对角线元素和相等且元素各不相同
return len(set(sums)) == 1 and set(nums) == set(range(1, r*c+1))
count = 0 # 计数器
dims = 3 # 三维幻方
for r in range(len(grid) - dims + 1): # 行
for c in range(len(grid[0]) - dims + 1): # 列
if is_magic_square(get_square(grid, c, r, c+dims, r+dims)):
count += 1
return count
另一种方案，如果有些基础知识的话，可以编程找到所有的幻方，3*3幻方总共有8种，通过查找可以快速获得一个方格是否是幻方。
class Solution(object):
def numMagicSquaresInside(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
l = [[8, 1, 6, 3, 5, 7, 4, 9, 2],
[6, 1, 8, 7, 5, 3, 2, 9, 4],
[4, 9, 2, 3, 5, 7, 8, 1, 6],
[2, 9, 4, 7, 5, 3, 6, 1, 8],
[6, 7, 2, 1, 5, 9, 8, 3, 4],
[8, 3, 4, 1, 5, 9, 6, 7, 2],
[2, 7, 6, 9, 5, 1, 4, 3, 8],
[4, 3, 8, 9, 5, 1, 2, 7, 6]]
count = 0
for i in range(len(grid) - 2):
for j in range(len(grid[0]) - 2):
temp = grid[i][j:j + 3] + grid[i + 1][j:j + 3] + grid[i + 2][j:j + 3]
if temp in l:
count += 1
return count
如有疑问或建议，欢迎评论区留言~
