A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 "magic square" subgrids are there?  (Each subgrid is contiguous).

 

Example 1:

Input: [[4,3,8,4],        [9,5,1,9],        [2,7,6,2]]Output: 1Explanation: The following subgrid is a 3 x 3 magic square:438951276while this one is not:384519762In total, there is only one magic square inside the given grid.

Note:

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

 

思路就是依次扫, 只是利用

Here I just want share two observatons with this 1-9 condition:

 

Assume a magic square:

a1,a2,a3

a4,a5,a6

a7,a8,a9

 

a2 + a5 + a8 = 15

a4 + a5 + a6 = 15

a1 + a5 + a9 = 15

a3 + a5 + a7 = 15

 

Accumulate all, then we have:

sum(ai) + 3 * a5 = 60

3 * a5 = 15

a5 = 5

 

The center of magic square must be 5.  这个条件来去减少一些判断.

 

Code:

class Solution:    def numMagicSquaresInside(self, grid):        ans, lrc = 0, [len(grid), len(grid[0])]        def checkMagic(a,b, c, d, e, f, g ,h, i):            return (sorted([a,b,c,d,e,f,g,h,i]) == [i for i in range(1,10)] and                    (a + b+c == d + e + f == g + h + i == a + d + g == b + e + h == c +f + i                   == a + e + i == c +  e + g == 15))        for i in range(1, lrc[0]-1):            for j in range(1, lrc[1]-1):                if grid[i][j] == 5 and checkMagic(grid[i-1][j-1], grid[i-1][j], grid[i-1][j+1],                             grid[i][j-1], grid[i][j], grid[i][j+1],                             grid[i+1][j-1], grid[i+1][j], grid[i+1][j+1]):                    ans += 1        return ans