[每日 LeetCode] 840. 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

思路：题目要求找出高维数组中的魔方数，暂时能做的方法就是从第二行开始依次遍历高维数组，以该点为中心判断是否符合魔方数规则，特别注意元素下标。魔方数规则如下（第三条容易不注意）：
1.中间的数是 5
2.每行每列交叉 8 组数的和为 15
3.9 个数的和为 45 且积为 362880
（此条规则可排除特殊用例：[[5,5,5],[5,5,5],[5,5,5]]）

我的 C++ 代码

class Solution {
public:
    bool magic(vector<vector<int>>& g, int x, int y) {
        int a = 0, b = 1;  
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                int c = g[i+x][j+y];
                a += c;
                b *= c;
            }
        } 
        return 
            a == 45 && b == 362880 &&
            g[x][y] + g[x][y+1] + g[x][y+2] == 15 &&
            g[x+1][y] + g[x+1][y+1] + g[x+1][y+2] == 15 &&
            g[x+2][y] + g[x+2][y+1] + g[x+2][y+2] == 15 &&
            g[x][y] + g[x+1][y] + g[x+2][y] == 15 &&
            g[x][y+1] + g[x+1][y+1] + g[x+2][y+1] == 15 &&
            g[x][y+2] + g[x+1][y+2] + g[x+2][y+2] == 15 &&
            g[x][y] + g[x+1][y+1] + g[x+2][y+2] == 15 &&
            g[x+2][y] + g[x+1][y+1] + g[x][y+2] == 15;
    }
    
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int result = 0;        
        for(int i = 0; i + 2 < m; i++) {
            for(int j = 0; j + 2 < n; j++) {
                if(magic(grid, i, j)) result++;
            }
        }
        return result;
    }
};
​

运行时间：4ms
运行内存：9.2M