※ 引述《JIWP (神楽めあ的钱包)》之铭言：
: 这题满无聊的
: 用暴力法就可以了
: 写起来超丑
: 840. Magic Squares In Grid
: magic square是指3*3的grid包含1~9
: 每个数字只会出现一次
: 且每行、每列、对角线的总和都会一样
: 给你一个row*col grid请求出有几个magic square
: 思路:
: 因为1~9的等差数列总合为45
: 然后每行、每列的总和要相等 : 45/3=15
: 15就是那个总和
: 然后要达到magic square，中心一定要是5
: 确认条件后就for循环下去检查
: 就可以得到答案了
: golang code：
: func numMagicSquaresInside(grid [][]int) int {
: n, m, ans := len(grid), len(grid[0]), 0
: if n < 3 || m < 3 {
: return 0
: }
: for i := 0; i < n-2; i++ {
: for j := 0; j < m-2; j++ {
: ans += chk(grid, i, j)
: }
: }
: return ans
: }
: func chk(arr [][]int, i, j int) int {
: rec := make([]bool, 9)
: if arr[i+1][j+1] != 5 {
: return 0
: }
: diagonal_1, diagonal_2 := arr[i][j]+arr[i+1][j+1]+arr[i+2][j+2], arr[i][j+2]+
: arr[i+1][j+1]+arr[i+2][j]
: if diagonal_1 != 15 || diagonal_2 != 15 {
: return 0
: }
: c_sum := [3]int{}
: for x := i; x < i+3; x++ {
: r_sum := 0
: c_sum[0] += arr[x][j]
: c_sum[1] += arr[x][j+1]
: c_sum[2] += arr[x][j+2]
: for y := j; y < j+3; y++ {
: if arr[x][y] > 9 || arr[x][y] == 0 || rec[arr[x][y]-1] {
: return 0
: }
: rec[arr[x][y]-1] = true
: r_sum += arr[x][y]
: }
: if r_sum != 15 {
: return 0
: }
: }
: for i := 0; i < 3; i++ {
: if c_sum[i] != 15 {
: return 0
: }
: }
: return 1
: }
先补昨天的
思路:
照叙述暴力解 所以很丑
写个函数确认是否符合要求
另外magic square中间必为5
所以遇到5再确认就好
Python Code:
class Solution:
def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
def check(matrix: List[List[int]]) -> bool:
validity = {1, 2, 3, 4, 5, 6, 7, 8, 9}
if set(matrix[0] + matrix[1] + matrix[2]) != validity:
return False
for i in range(3):
if sum(matrix[i]) != 15 or sum(row[i] for row in matrix) !=
15:
return False
if matrix[0][0] + matrix[1][1] + matrix[2][2] != 15 or
matrix[0][2] + matrix[1][1] + matrix[2][0] != 15:
return False
return True
r = len(grid)
c = len(grid[0])
result = 0
for i in range(r - 2):
for j in range(c - 2):
if grid[i + 1][j + 1] == 5:
matrix = [grid[i][j:j+3], grid[i+1][j:j+3],
grid[i+2][j:j+3]]
if check(matrix):
result += 1
return result