leetcode-840-Magic Squares In Grid

题目描述:

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

要完成的函数:

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

说明:

1、这道题给定一个二维的vector,也就是一个矩阵,要求判断这个矩阵中含有多少个magic三维矩阵,返回数量。

magic三维矩阵的定义是,所有数值都在1-9之间(闭区间),且每一行、每一列和每条对角线的和都相等(也就是15)。

2、这是一道简单题,我们直接暴力处理就好了。

首先,我们判断每个子矩阵的中心点是不是为5。这一步可以过滤掉很多子矩阵。

接着,判断符号第一个条件的子矩阵的所有9个数,是不是都在1-9之间。在测试样例中,出现了包含0和10这样的数的子矩阵,也可以形成magic矩阵。

最后,判断三行、三列和两条对角线的和是否为15。

代码构造如下:(附详解)

    int numMagicSquaresInside(vector<vector<int>>& grid) 
    {
        int hang=grid.size(),lie=grid[0].size(),res=0;
        for(int i=1;i<=lie-2;i++)
        {
            for(int j=1;j<=lie-2;j++)//从第二行第二列开始判断中心点,直到倒数第二行倒数第二列结束
            {
                if(grid[i][j]==5)//满足第一个条件
                {
                    if(grid[i-1][j-1]<=9&&grid[i-1][j-1]>=1&&
                      grid[i-1][j]<=9&&grid[i-1][j]>=1&&
                      grid[i-1][j+1]<=9&&grid[i-1][j+1]>=1&&
                      grid[i][j-1]<=9&&grid[i][j-1]>=1&&
                      grid[i][j+1]<=9&&grid[i][j+1]>=1&&
                      grid[i+1][j-1]<=9&&grid[i+1][j-1]>=1&&
                      grid[i+1][j]<=9&&grid[i+1][j]>=1&&
                      grid[i+1][j+1]<=9&&grid[i+1][j+1]>=1)//判断是否都在1-9之间
                    {
                        if((grid[i-1][j-1]+grid[i-1][j]+grid[i-1][j+1]==15)&&
                           (grid[i][j-1]+grid[i][j]+grid[i][j+1]==15)&&
                           (grid[i+1][j-1]+grid[i+1][j]+grid[i+1][j+1]==15)&&
                           (grid[i-1][j-1]+grid[i][j-1]+grid[i+1][j-1]==15)&&
                           (grid[i-1][j]+grid[i][j]+grid[i+1][j]==15)&&
                           (grid[i-1][j+1]+grid[i][j+1]+grid[i+1][j+1]==15)&&
                           (grid[i-1][j-1]+grid[i][j]+grid[i+1][j+1]==15)&&
                           (grid[i-1][j+1]+grid[i][j]+grid[i+1][j-1]==15))//判断三行三列和两条对角线的和是否为15
                            res++;
                    }
                }
            }
        }
        return res;
    }

上述代码实测5ms,因为服务器没有充分的提交量,所以没有打败的百分比。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券