Magic Squares In Grid

Description

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 an grid of integers, how many 3 x 3 "magic square" subgrids are there? (Each subgrid is contiguous).

Example 1:

Input: [[4,3,8,4],
        [9,5,1,9],
        [2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.

Note:

1. 1 <= grid.length <= 10

2. 1 <= grid[0].length <= 10

3. 0 <= grid[i][j] <= 15

Solution

Reference: https://leetcode.com/problems/magic-squares-in-grid/discuss/133874/Python-5-and-43816729

class Solution {
public:
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        static vector<int> order = {4,9,2,7,6,1,8,3,4,9,2,7,6,1,8}; // clockwise order
        static vector<int> rorder(order.rbegin(), order.rend());
        // indices[i]: the starting index in `order`, for i = 2,4,6,8
        static vector<int> indices = {0,0,2,0,0,0,4,0,6};
        int count = 0;
        for(int i = 0; i + 2 < grid.size(); ++i){
            for(int j = 0; j + 2 < grid[0].size(); ++j){
                // the center must be 5, and the top-left number must be even
                if(grid[i + 1][j + 1] != 5) continue;
                int topleft = grid[i][j];
                if(topleft % 2 || topleft > 8 || topleft == 0) continue; // topleft must be 2, 4, 6, 8
                int idx = indices[topleft];
                // check if the other numbers are in correct order
                if(isMagic(grid, i, j, order.begin() + idx) || isMagic(grid, i, j, rorder.begin() + 6 - idx))
                    ++count;
            }
        }
        return count;
    }
    
    bool isMagic(vector<vector<int>> &grid, int i, int j, vector<int>::iterator it){
        static vector<int> xs = {0,1,2,5,8,7,6,3};
        for(int x : xs){
            if(grid[i + x / 3][j + x % 3] != *it)
                return false;
            ++it;
        }
        return true;
    }
};