840. Magic Squares In Grid

[zeikar]

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