Leetcode 840 Magic Squares In Grid

发表于 |

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: 1
Explanation:
The following subgrid is a 3 x 3 magic square:
438
951
276
while this one is not:
384
519
762
In total, there is only one magic square inside the given grid.

Note:
1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15

分析：
题目定义了一个概念，3x3的矩阵，元素从1到9，横纵对角线之和相等，把这个称为”magic square”，给定一个二维列表，找有多少个magic square，数据长度不超过10 x 10，说明这道题随便写都不会超时

思路：
从1到9取值，那么最中间的数必是5，至于为什么，想不通的我建议你放弃，只要从1，1到n-1,n-1遍历，如果满足值为5就进行判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def numMagicSquaresInside(grid):
	m,n = len(grid),len(grid[0])
	res = 0

	def isMagic(i,j):
		for x,y in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,1)]:
			if grid[i+x][j+y] > 9 or grid[i+x][j+y] < 1: return False
		return grid[i-1][j-1]+grid[i+1][j+1] == grid[i+1][j-1]+grid[i-1][j+1] == grid[i][j-1]+grid[i][j+1] == grid[i+1][j]+grid[i-1][j] 
	for i in range(1,m-1):
		for j in range(1,n-1):
			if grid[i][j] == 5 and isMagic(i,j): res += 1
	return res


87 / 87 test cases passed.
difficulty: easy
Runtime: 33 ms