题目描述

3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。

给定一个由整数组成的矩阵 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。

样例

输入: [[4,3,8,4],
      [9,5,1,9],
      [2,7,6,2]]
输出: 1
解释: 
下面的子矩阵是一个 3 x 3 的幻方：
438
951
276

而这一个不是：
384
519
762

总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。

注意

• 1 <= grid.length = grid[0].length <= 10
• 0 <= grid[i][j] <= 15

算法

(暴力枚举) $O(n^2)$

1. 枚举所有可能的左上角，然后按规则判断即可。
2. 合法的 3 x 3 的幻方矩阵，每行每列和对角线的和一定都是 15。

时间复杂度

• 枚举所有可能的左上角，常数时间判断，故时间复杂度为 $O(nm)$。

空间复杂度

• 只需要常数的额外空间。

C++ 代码

class Solution {
public:

    bool check(int x, int y, const vector<vector<int>>& grid) {
        vector<int> vis(10, false);
        int row = 0, col = 0;

        for (int i = x; i < x + 3; i++) {
            int tmp = 0;
            for (int j = y; j < y + 3; j++) {
                if (grid[i][j] >= 10 || vis[grid[i][j]])
                    return false;
                tmp += grid[i][j];
                vis[grid[i][j]] = true;
            }
            if (tmp != 15)
                return false;
        }

        for (int j = y; j < y + 3; j++) {
            int tmp = 0;
            for (int i = x; i < x + 3; i++)
                tmp += grid[i][j];
            if (tmp != 15)
                return false;
        }

        if (grid[x][y] + grid[x + 1][y + 1] + grid[x + 2][y + 2] != 15)
            return false;
        if (grid[x][y + 2] + grid[x + 1][y + 1] + grid[x + 2][y] != 15)
            return false;

        return true;
    }

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