LeetCode 840. 矩阵中的幻方（数学）

Michael阿明

发布于 2020-07-13 16:12:19

6440

发布于 2020-07-13 16:12:19

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

1. 题目

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/magic-squares-in-grid 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 证明中间必须是5

C_1+C_9=15-C_5

C_3+C_7=15-C_5

C_2+C_8=15-C_5

C_1+C_2+C_3+C_7+C_8+C_9=15-C_5+15-C_5+C_2+C_8

即

30=15-C_5+15-C_5+C_2+C_8=45-3*C_5

C_5=5

class Solution {
	int x, y, sum;
	int nb[10];
public:
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), i, j, count = 0;
        for(i = 0; i <= m-3; ++i)
        	for(j = 0; j <= n-3; ++j)
        	{
        		if(grid[i+1][j+1] != 5)//中间必须是5
        			continue;
        		if(isMagic(i,j,grid))
        			count++;
        	}
    	return count;
    }

    bool isMagic(int &i, int &j, vector<vector<int>>& grid)
    {
    	memset(nb,0,sizeof nb);
    	for(x=i; x<i+3; ++x)
    	{
    		sum = 0;
    		for(y=j; y<j+3; ++y)
    		{
    			sum += grid[x][y];//横向
    			if(grid[x][y]>=1 && grid[x][y]<=9 && nb[grid[x][y]]==0)
    				nb[grid[x][y]] = 1;//判断是否只有1-9，且不重复的数
    		}
    		if(sum != 15)
				return false;
    	}
    	sum = 0;
    	for(x = 1; x <= 9; ++x)
    		sum += nb[x];
    	if(sum != 9)//判断是否只有1-9，且不重复的数
    		return false;
    	for(y=j; y<j+3; ++y)
    	{
    		sum = 0;
    		for(x=i; x<i+3; ++x)
    			sum += grid[x][y];//纵向
    		if(sum != 15)
				return false;
    	}
    	sum = grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2];//对角线
    	if(sum != 15)
			return false;
		return grid[i+2][j]+grid[i+1][j+1]+grid[i][j+2] == 15;//对角线
    }
};