Problem link
https://leetcode.com/problems/magic-squares-in-grid/
Problem Summary
2d 그리드가 주어질 때 안에서 magic square가 되는 부분 그리드의 개수를 구하는 문제.
Solution
그냥 돌려주면 된다.
1-9까지의 distinct가 나와야 되고 가로, 세로, 대각선의 합이 다 같은지 확인한다.
최적화?
magic square의 특성을 잘 분석해보면 간단하게 풀 수 있다.
일단 행, 열, 대각선을 더해서 다 같으려면 15가 나와야 한다.
그리고 적절히 식을 정리하면 가운데는 5가 나와야 한다. 이런식으로 수학적으로 풀면 특정 조합밖에 답이 안 되는데 lee형님 솔루션 또는 에디토리얼 참고.
Source Code
class Solution:
def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
def check(x, y):
# distinct check
visited = set()
for i in range(3):
for j in range(3):
if grid[x + i][y + j] <= 0 or grid[x + i][y + j] >= 10:
return 0
visited.add(grid[x + i][y + j])
if len(visited) != 9:
return 0
# sum check
sums = set()
for i in range(3):
sum = 0
for j in range(3):
sum += grid[x + i][y + j]
sums.add(sum)
for j in range(3):
sum = 0
for i in range(3):
sum += grid[x + i][y + j]
sums.add(sum)
sum = 0
for i in range(3):
sum += grid[x + i][y + i]
sums.add(sum)
sum = 0
for i in range(3):
sum += grid[x + 2 - i][y + i]
sums.add(sum)
return len(sums) == 1
r = len(grid)
c = len(grid[0])
ans = 0
for i in range(r - 2):
for j in range(c - 2):
ans += check(i, j)
return ans