leetcode-840-Magic Squares In Grid

chenjx85

发布于 2019-03-15 17:17:51

4590

发布于 2019-03-15 17:17:51

题目描述：

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 <= grid.length <= 10
1 <= grid[0].length <= 10
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，因为服务器没有充分的提交量，所以没有打败的百分比。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-05-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除

grid