中文个人网站欣赏,wordpress上不去,用dw做网站维护教程,做的好的个人网站知乎1. 题目
3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵#xff0c;其中每行#xff0c;每列以及两条对角线上的各数之和都相等。
给定一个由整数组成的 grid#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵#xff1f;#xff08;每个子矩阵都是连续的其中每行每列以及两条对角线上的各数之和都相等。
给定一个由整数组成的 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 C1C915−C5C_1C_915-C_5C1C915−C5 C3C715−C5C_3C_715-C_5C3C715−C5 C2C815−C5C_2C_815-C_5C2C815−C5 C1C2C3C7C8C915−C515−C5C2C8C_1C_2C_3C_7C_8C_915-C_515-C_5C_2C_8C1C2C3C7C8C915−C515−C5C2C8 即 3015−C515−C5C2C845−3∗C53015-C_515-C_5C_2C_845-3*C_53015−C515−C5C2C845−3∗C5 C55C_55C55
class Solution {int x, y, sum;int nb[10];
public:int numMagicSquaresInside(vectorvectorint 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[i1][j1] ! 5)//中间必须是5continue;if(isMagic(i,j,grid))count;}return count;}bool isMagic(int i, int j, vectorvectorint grid){memset(nb,0,sizeof nb);for(xi; xi3; x){sum 0;for(yj; yj3; 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(yj; yj3; y){sum 0;for(xi; xi3; x)sum grid[x][y];//纵向if(sum ! 15)return false;}sum grid[i][j]grid[i1][j1]grid[i2][j2];//对角线if(sum ! 15)return false;return grid[i2][j]grid[i1][j1]grid[i][j2] 15;//对角线}
};
