目录

• 题目描述：
• 示例：
• 解法：

题目描述：

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. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. 0 <= grid[i][j] <= 15

---

解法：

class Solution {
public:
    bool valid(vector<vector<int>>& grid, int x, int y){
        vector<bool> flag(10, false);
        for(int dx = 0; dx < 3; dx++){
            int row_val = 0;
            int col_val = 0;
            for(int dy = 0; dy < 3; dy++){
                int val = grid[x+dx][y+dy];
                flag[val] = true;
                row_val += grid[x+dx][y+dy];
                col_val += grid[x+dy][y+dx];
            }
            if(row_val != 15 || col_val != 15){
                return false;
            }
        }
        if(grid[x][y] + grid[x+1][y+1] + grid[x+2][y+2] != 15){
            return false;
        }
        if(grid[x+2][y] + grid[x+1][y+1] + grid[x][y+2] != 15){
            return false;
        }
        for(int i = 1; i <= 9; i++){
            if(!flag[i]){
                return false;
            }
        }
        return true;
    }
    
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        if(m < 3 || n < 3){
            return 0;
        }else{
            int res = 0;
            for(int i = 0; i < m-2; i++){
                for(int j = 0; j < n-2; j++){
                    if(valid(grid, i, j)){
                        res++;
                    }
                }
            }
            return res;
        }
    }
};