[LeetCode] 840. Magic Squares In Grid

https://leetcode.com/problems/magic-squares-in-grid/description/?envType=daily-question&envId=2024-08-09

leetcode - Magic Squares In Grid

문제 유형 : 행렬

문제 난이도 : Medium

 

문제

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given a row x col grid of integers, how many 3 x 3 contiguous magic square subgrids are there?

Note: while a magic square can only contain numbers from 1 to 9, grid may contain numbers up to 15.

 

3 x 3의 매직 정사각형은 1에서 9까지 3 x 3으로 채워지고 모든 가로, 세로, 대각선의 합이 같은 정사각형을 말한다.

row x col의 크기의 정수 행렬이 주어진다.

몇 개의 매직 정사각형을 찾을 수 있는가?

Note: grid의 값은 0~15까지이다.

 

풀이

맨 왼쪽 위를 기준점으로 하여 3 x 3정사각형 행렬이 매직인지 확인하고 카운트를 1 늘인다.

인덱스가 빠져나오지 않도록 반복을 row-2, col-2까지만 해야한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    bool isMagicSquare(int r, int c, vector<vector<int>>& grid) {
        vector<bool> table(9, false);
        vector<int> sums(8, 0);
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                int val = grid[i+r][j+c];
                if(val < 1 || val > 9 || table[val-1]) return false;
                table[val-1] = true;
                sums[i] += val;
                sums[3+j] += val;
            }
        }
        sums[6] = grid[r][c] + grid[r+2][c+2] + grid[r+1][c+1];
        sums[7] = grid[r][c+2] + grid[r+2][c] + grid[r+1][c+1];

        for(int i = 1; i < 8; i++) {
            if(sums[0] != sums[i]) return false;
        }
        return true;
    }

    int numMagicSquaresInside(vector<vector<int>>& grid) {
        int ans = 0;
        int n = grid.size();
        int m = grid[0].size();
        for(int i = 0; i < n-2; i++) {
            for(int j = 0; j < m-2; j++) {
                if(isMagicSquare(i, j, grid)) ans++;
            }
        }

        return ans;
    }
};