文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Largest Magic Square
2. Solution
解析：根据幻方定义，分别检查主对角线、副对角线、各行、各列的和是否相等，按阶次从大到小依次检查，碰到满足条件的返回阶。
- Version 1
class Solution:
def largestMagicSquare(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
size = min(m, n)
for k in range(size, 0, -1):
for i in range(m-k+1):
for j in range(n-k+1):
if self.check(grid, i, j, k):
return k
def check(self, grid, x, y, k):
main_diagonal = 0
secondary_diagonal = 0
for i in range(k):
main_diagonal += grid[x+i][y+i]
secondary_diagonal += grid[x+i][y+k-i-1]
if main_diagonal != secondary_diagonal:
return False
for i in range(k):
row = sum(grid[x+i][y:y+k])
if row != main_diagonal:
return False
column = sum([grid[x+j][y+i] for j in range(k)])
if column != main_diagonal:
return False
return True
