840-magic-squares-in-grid.md

840. Magic Squares In Grid - 矩阵中的幻方

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

给定一个由整数组成的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。

 

示例：

输入: [[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 的幻方子矩阵。

提示:

1. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. 0 <= grid[i][j] <= 15

---

题目标签：Array

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
python3	44 ms	N/A

class Solution:
    def numMagicSquaresInside(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if len(grid) < 3 or len(grid[0]) < 3:
            return 0
        res = 0
        for i in range(1, len(grid)-1):
            for j in range(1, len(grid[0])-1):
                aa = []
                aaa = []
                for x in (-1, 0, 1):
                    aa.append([])
                    for y in (-1, 0, 1):
                        aa[-1].append(grid[i+x][j+y])
                        aaa.append(grid[i+x][j+y])
                if len(set(filter(lambda a: 1 <= a <= 9, aaa))) == 9:
                    tmp = []
                    tmp.extend([sum(aa[z]) for z in range(3)])
                    tmp.extend([sum(list(zip(*aa))[z]) for z in range(3)])
                    tmp.append(aa[0][0] + aa[1][1] + aa[2][2])
                    tmp.append(aa[0][2] + aa[1][1] + aa[2][0])
                    if len(set(tmp)) == 1:
                        res += 1
        return res