3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。
给定一个由整数组成的row x col 的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？
注意：虽然幻方只能包含 1 到 9 的数字，但 grid 可以包含最多15的数字。
示例 1：
输入: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2] 输出: 1 解释: 下面的子矩阵是一个 3 x 3 的幻方：而这一个不是：
总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
示例 2:
输入: grid = [[8]] 输出: 0
提示:
登录row == grid.lengthcol == grid[i].length1 <= row, col <= 100 <= grid[i][j] <= 15$3\times 3$ 的幻方必须包含 $1$ 到 $9$ 所有数字，这意味着幻方元素和为 $1+2+\cdots + 9 = 45$。
由于每行的和都要相等，所以每行的和为 $\dfrac{45}{3} = 15$。这也是每列的和，对角线的和。
有 $4$ 条经过幻方正中心的线：第二行，第二列，两条对角线。
这 $4$ 条线：
设正中心的数为 $x$ ，则有
$$
1+2+\cdots + 9 + 3x = 60
$$
解得
$$
x = 5
$$
换言之（逆否命题），如果 $3\times 3$ 矩阵正中心的数不是 $5$，那么该矩阵必然不是幻方。
如果 $3\times 3$ 矩阵包含 $1$ 到 $9$ 所有整数，且前两行的和都是 $15$，那么第三行的和为
$$
1+2+\cdots+9-15-15 = 15
$$
同理，如果前两列的和都是 $15$，那么第三列的和必然是 $15$。
如果 $3\times 3$ 矩阵：
下面证明：矩阵对角线的和一定都是 $15$。
设矩阵为
$$
\begin{bmatrix}
a & b & c \
d & 5 & f \
g & h & i \
\end{bmatrix}
$$
由于正中心的数是 $5$，只需证明对角两数之和等于 $10$，即 $a+i=c+g=10$。
在 $1$ 到 $9$ 中选两个不同整数相加等于 $10$，只有如下 $4$ 种情况：
由于已知 $b+h=d+f=10$，消耗了两种情况，剩余的四个数必然在 $a,c,g,i$ 中。比如 $b+h=1+9$，$d+f=3+7$，那么剩余的 $2,4,6,8$ 必然在 $a,c,g,i$ 中。
比如左上角的 $a=4$，那么 $6$ 在哪？
用同样的方法可以证明，$a$ 等于其他数的时候，对角的数 $i$ 一定等于 $10-a$。剩余的另一对和为 $10$ 的数在另一对角。
综上，由已知条件可得，两条对角线的和都是 $15$。
如何快速判断矩阵包含 $1$ 到 $9$ 所有数？可以把数字压缩到一个二进制数 $\textit{mask}$ 中，$\textit{mask}$ 从低到高的 $i$ 位是 $1$ 表示 $i$ 在矩阵中。矩阵包含 $1$ 到 $9$ 所有数相当于 $\textit{mask} = 1111111110_{(2)} = 2^{10}-2=1022$。
###py
class Solution:
def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
ans = 0
for i in range(m - 2):
for j in range(n - 2):
if grid[i + 1][j + 1] != 5:
continue
mask = 0
r_sum = [0] * 3
c_sum = [0] * 3
for r in range(3):
for c in range(3):
x = grid[i + r][j + c]
mask |= 1 << x
r_sum[r] += x
c_sum[c] += x
if mask == 1022 and r_sum[0] == r_sum[1] == c_sum[0] == c_sum[1] == 15:
ans += 1
return ans
###java
class Solution {
public int numMagicSquaresInside(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int ans = 0;
for (int i = 0; i < m - 2; i++) {
for (int j = 0; j < n - 2; j++) {
if (grid[i + 1][j + 1] != 5) {
continue;
}
int mask = 0;
int[] rSum = new int[3];
int[] cSum = new int[3];
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
int x = grid[i + r][j + c];
mask |= 1 << x;
rSum[r] += x;
cSum[c] += x;
}
}
if (mask == (1 << 10) - 2 &&
rSum[0] == 15 && rSum[1] == 15 &&
cSum[0] == 15 && cSum[1] == 15) {
ans++;
}
}
}
return ans;
}
}
###cpp
class Solution {
public:
int numMagicSquaresInside(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int ans = 0;
for (int i = 0; i < m - 2; i++) {
for (int j = 0; j < n - 2; j++) {
if (grid[i + 1][j + 1] != 5) {
continue;
}
int mask = 0;
int r_sum[3]{};
int c_sum[3]{};
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
int x = grid[i + r][j + c];
mask |= 1 << x;
r_sum[r] += x;
c_sum[c] += x;
}
}
if (mask == (1 << 10) - 2 &&
r_sum[0] == 15 && r_sum[1] == 15 &&
c_sum[0] == 15 && c_sum[1] == 15) {
ans++;
}
}
}
return ans;
}
};
###c
int numMagicSquaresInside(int** grid, int gridSize, int* gridColSize) {
int m = gridSize, n = gridColSize[0];
int ans = 0;
for (int i = 0; i < m - 2; i++) {
for (int j = 0; j < n - 2; j++) {
if (grid[i + 1][j + 1] != 5) {
continue;
}
int mask = 0;
int r_sum[3] = {};
int c_sum[3] = {};
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
int x = grid[i + r][j + c];
mask |= 1 << x;
r_sum[r] += x;
c_sum[c] += x;
}
}
if (mask == (1 << 10) - 2 &&
r_sum[0] == 15 && r_sum[1] == 15 &&
c_sum[0] == 15 && c_sum[1] == 15) {
ans++;
}
}
}
return ans;
}
###go
func numMagicSquaresInside(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
for i := range m - 2 {
for j := range n - 2 {
if grid[i+1][j+1] != 5 {
continue
}
mask := 0
var rSum, cSum [3]int
for r, row := range grid[i : i+3] {
for c, x := range row[j : j+3] {
mask |= 1 << x
rSum[r] += x
cSum[c] += x
}
}
if mask == 1<<10-2 &&
rSum[0] == 15 && rSum[1] == 15 &&
cSum[0] == 15 && cSum[1] == 15 {
ans++
}
}
}
return
}
###js
var numMagicSquaresInside = function (grid) {
const m = grid.length;
const n = grid[0].length;
let ans = 0;
for (let i = 0; i < m - 2; i++) {
for (let j = 0; j < n - 2; j++) {
if (grid[i + 1][j + 1] !== 5) {
continue;
}
let mask = 0;
const rSum = [0, 0, 0];
const cSum = [0, 0, 0];
for (let r = 0; r < 3; r++) {
for (let c = 0; c < 3; c++) {
const x = grid[i + r][j + c];
mask |= 1 << x;
rSum[r] += x;
cSum[c] += x;
}
}
if (mask === (1 << 10) - 2 &&
rSum[0] === 15 && rSum[1] === 15 &&
cSum[0] === 15 && cSum[1] === 15) {
ans++;
}
}
}
return ans;
};
###rust
impl Solution {
pub fn num_magic_squares_inside(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut ans = 0;
for i in 0..m.saturating_sub(2) {
for j in 0..n.saturating_sub(2) {
if grid[i + 1][j + 1] != 5 {
continue;
}
let mut mask = 0;
let mut r_sum = [0; 3];
let mut c_sum = [0; 3];
for (r, row) in grid[i..i + 3].iter().enumerate() {
for (c, &x) in row[j..j + 3].iter().enumerate() {
mask |= 1 << x;
r_sum[r] += x;
c_sum[c] += x;
}
}
if mask == (1 << 10) - 2 &&
r_sum[0] == 15 && r_sum[1] == 15 &&
c_sum[0] == 15 && c_sum[1] == 15 {
ans += 1;
}
}
}
ans
}
}
欢迎关注 B站@灵茶山艾府
首先谈谈三阶幻方，固然是可以通过定义去判断，但写起来很麻烦，效率也不高。实际上，三阶幻方的解是固定的，有以下八种。
自然是不可能逐个判断是不是这八个之一，大家仔细观察，相信很容易找出这八个解的共同点，首先中间的元素都是五，角上元素都是偶数，中点都是奇数。同一行的解可以通过旋转得到，第一行镜像，可以得到第二行。也就是说，三阶幻方本质只有一种解，其余都是旋转镜像的体现。
我们可以依据这一点，写出优雅简洁的代码。
###cpp
class Solution {
public:
vector<int> m={8,1,6,7,2,9,4,3,8,1,6,7,2,9,4,3};
int numMagicSquaresInside(vector<vector<int>>& grid) {
int di[8]={-1,-1,-1,0,1,1,1,0};
int dj[8]={-1,0,1,1,1,0,-1,-1};
int count=0;
for(int i=1;i<grid.size()-1;i++)
for(int j=1;j<grid[0].size()-1;j++)
if(grid[i][j]==5){
vector<int> around;
for(int k=0;k<8;k++)
around.push_back(grid[i+di[k]][j+dj[k]]);
count+=IsMagic(around);
}
return count;
}
bool IsMagic(vector<int>& v){
for(int i=0;i<8;i+=2)
if(m[i]==v[0])
return v==vector<int>(m.begin()+i,m.begin()+i+8)
||v==vector<int>(m.rbegin()+7-i,m.rbegin()+15-i);
return false;//奇数元素
}
};
满足幻方的条件必定是中间的数字为5,周围的数字为满足 1->6->7->2->9->4->3->8->1
的这种圆环结构,5的上下左右必定是 1、9、3、7(这四个数字都只能组成两组 15)
并且5的周围的数字其实都可以跳过,这里没作实现
1.利用数组的索引语义记录索引对应的下一个数字
2.若5的下一个值满足条件,且该值的下一行对应列满足条件,顺时针
若5的下一个值满足条件,且该值的上一行对应列满足条件,逆时针
3.总共判断6次即可(前两次已经判断过了)
###java
class Solution {
public int numMagicSquaresInside(int[][] grid) {
//if(grid == null || grid.length < 3 || grid[1].length < 3)return 0;
//由于是1~9的不同数字,那么必定是5在中间,并且其他数字满足顺时针或逆时针
int[] check = {0,6,9,8,3,0,7,2,1,4};
int result = 0;
for(int i=1;i<grid.length-1;i++){
for(int j=1;j<grid[0].length-1;j++){
if(grid[i][j] == 5){
int next = grid[i][j+1];
switch(next){
case 1:
case 3:
case 7:
case 9:
if(check[next] == grid[i+1][j+1]){
if(each(grid,check,i+1,j+1,1))
result++;
}else if(check[next] == grid[i-1][j+1]){
if(each(grid,check,i-1,j+1,-1))
result++;
}
}
//5的后一位必定不用算
j++;
}
}
}
return result;
}
public boolean each(int[][] grid,int[] check,int x,int y,int ward){
int cur = grid[x][y];
int next = check[cur];
for(int i=y-2;y!=i;){
if(grid[x][--y] != next)
return false;
cur = next;
next = check[cur];
}
for(int i=x-2*ward;x!=i;){
if(grid[x-=ward][y] != next)
return false;
cur = next;
next = check[cur];
}
for(int i=y+2;y!=i;){
if(grid[x][++y] != next)
return false;
cur = next;
next = check[cur];
}
return true;
}
}
