Leetcode840.Magic Squares In Grid矩阵中的幻方

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

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

示例 1:

输入: [[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

注意题目中说的是1到9的数字

class Solution {

public:

    int numMagicSquaresInside(vector<vector<int> >& grid) {

        int res = 0;

        int r = grid.size();

        int c = grid[0].size();

        for(int i = 0; i <= r - 3; i++)

        {

            for(int j = 0; j <= c - 3; j++)

            {

                bool check = true;

                int flag = grid[i][j] + grid[i][j + 1] + grid[i][j + 2];

                if(  grid[i + 1][j] + grid[i + 1][j + 1] + grid[i + 1][j + 2] != flag

                   ||grid[i + 2][j] + grid[i + 2][j + 1] + grid[i + 2][j + 2] != flag

                   ||grid[i][j] + grid[i + 1][j + 1] + grid[i + 2][j + 2] != flag

                   ||grid[i + 2][j] + grid[i + 1][j + 1] + grid[i][j + 2] != flag)

                   {

                       check = false;

                   }

                for(int y = i; y <= i + 2; y++)

                    for(int x = j; x <= j + 2; x++)

                    if(grid[y][x] > 9 || grid[y][x] <= 0)

                {

                    check = false;

                    break;

                }

                if(check)

                    res++;

            }

        }

        return res;

    }

};

巴特西

Leetcode840.Magic Squares In Grid矩阵中的幻方

最新文章

热门文章