※ 引述《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