算法题矩阵中的幻方-平芜编程栈

840. 矩阵中的幻方

问题描述

3×3 幻方是一个填充了从 1 到 9 的不同数字的 3×3 网格，其中每行、每列以及两条对角线的和都等于15。

给定一个row x col的整数矩阵grid，返回矩阵中3×3 幻方子矩阵的数量。

注意：

幻方必须包含数字 1-9，每个数字恰好出现一次
幻方的中心必须是 5（这是一个重要的数学性质）

示例：

输入:grid=[[4,3,8,4],[9,5,1,9],[2,7,6,2]]输出:1

4 3 8 4 9 5 1 9 2 7 6 2

只有左上角的 3×3 子矩阵是幻方：

4 3 8 9 5 1 2 7 6

算法思路

核心：
- 3×3 幻方必须包含数字 1-9 各一次
- 幻方的中心必须是 5
- 所有行、列、对角线的和必须等于 15
- 只有8 种可能的 3×3 幻方（通过旋转和镜像得到）
方法：
- 方法一：遍历所有可能的 3×3 子矩阵，逐一验证
- 方法二：利用中心必须为 5，只检查中心为 5 的位置
- 方法三：预计算所有8种幻方，直接匹配

代码实现

方法一：完整验证

classSolution{/** * 计算矩阵中3x3幻方的数量 * 3x3幻方：包含1-9各一次，每行/列/对角线和为15，中心必须为5 * * @param grid 输入矩阵 * @return 幻方数量 */publicintnumMagicSquaresInside(int[][]grid){introws=grid.length;intcols=grid[0].length;intcount=0;// 遍历所有可能的3x3子矩阵的左上角// 行范围：0 到 rows-3，列范围：0 到 cols-3for(inti=0;i<=rows-3;i++){for(intj=0;j<=cols-3;j++){// 幻方中心必须是5if(grid[i+1][j+1]==5){if(isMagicSquare(grid,i,j)){count++;}}}}returncount;}/** * 验证以(i,j)为左上角的3x3子矩阵是否为幻方 * * @param grid 原矩阵 * @param i 子矩阵左上角行索引 * @param j 子矩阵左上角列索引 * @return 是否为幻方 */privatebooleanisMagicSquare(int[][]grid,inti,intj){// 检查是否包含1-9各一次boolean[]seen=newboolean[10];// 索引0-9，使用1-9// 遍历3x3子矩阵的所有元素for(intr=0;r<3;r++){for(intc=0;c<3;c++){intnum=grid[i+r][j+c];// 数字必须在1-9范围内if(num<1||num>9){returnfalse;}// 检查是否重复if(seen[num]){returnfalse;}seen[num]=true;}}// 验证所有行的和为15for(intr=0;r<3;r++){if(grid[i+r][j]+grid[i+r][j+1]+grid[i+r][j+2]!=15){returnfalse;}}// 验证所有列的和为15for(intc=0;c<3;c++){if(grid[i][j+c]+grid[i+1][j+c]+grid[i+2][j+c]!=15){returnfalse;}}// 验证主对角线和为15if(grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2]!=15){returnfalse;}// 验证副对角线和为15if(grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j]!=15){returnfalse;}returntrue;}}

方法二：预计算所有幻方

importjava.util.*;classSolution{// 预计算所有8种3x3幻方（通过旋转和镜像得到）privatestaticfinalSet<String>MAGIC_SQUARES=newHashSet<>();static{// 基础幻方int[][]base={{4,3,8},{9,5,1},{2,7,6}};// 生成所有8种变体generateAllMagicSquares(base);}/** * 生成所有8种幻方并添加到集合中 */privatestaticvoidgenerateAllMagicSquares(int[][]base){// 4种旋转int[][]current=copyMatrix(base);for(inti=0;i<4;i++){MAGIC_SQUARES.add(matrixToString(current));current=rotate90(current);}// 镜像后的4种旋转int[][]mirrored=mirrorMatrix(base);current=copyMatrix(mirrored);for(inti=0;i<4;i++){MAGIC_SQUARES.add(matrixToString(current));current=rotate90(current);}}/** * 将3x3矩阵转换为字符串（用于哈希） */privatestaticStringmatrixToString(int[][]matrix){StringBuildersb=newStringBuilder();for(inti=0;i<3;i++){for(intj=0;j<3;j++){sb.append(matrix[i][j]);}}returnsb.toString();}/** * 顺时针旋转90度 */privatestaticint[][]rotate90(int[][]matrix){int[][]rotated=newint[3][3];for(inti=0;i<3;i++){for(intj=0;j<3;j++){rotated[j][2-i]=matrix[i][j];}}returnrotated;}/** * 水平镜像 */privatestaticint[][]mirrorMatrix(int[][]matrix){int[][]mirrored=newint[3][3];for(inti=0;i<3;i++){for(intj=0;j<3;j++){mirrored[i][j]=matrix[i][2-j];}}returnmirrored;}/** * 复制矩阵 */privatestaticint[][]copyMatrix(int[][]matrix){int[][]copy=newint[3][3];for(inti=0;i<3;i++){System.arraycopy(matrix[i],0,copy[i],0,3);}returncopy;}publicintnumMagicSquaresInside(int[][]grid){introws=grid.length;intcols=grid[0].length;intcount=0;for(inti=0;i<=rows-3;i++){for(intj=0;j<=cols-3;j++){// 快速检查中心是否为5if(grid[i+1][j+1]!=5){continue;}// 转换为字符串并检查是否在预计算集合中StringBuildersb=newStringBuilder();for(intr=0;r<3;r++){for(intc=0;c<3;c++){sb.append(grid[i+r][j+c]);}}if(MAGIC_SQUARES.contains(sb.toString())){count++;}}}returncount;}}

算法分析

时间复杂度：O((R-2) × (C-2)) = O(R×C)
- R 和 C 是矩阵的行数和列数
- 每个候选位置的验证是 O(1)（固定3×3大小）
空间复杂度：
- 方法一：O(1)（只使用固定大小的数组）
- 方法二：O(1)（预计算的8个幻方是常数空间）

算法过程

输入：grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]

矩阵尺寸：3行4列
可能的3×3子矩阵位置：
- 左上角 (0,0)：检查中心grid[1][1] = 5
- 左上角 (0,1)：检查中心grid[1][2] = 1（跳过）
验证位置 (0,0) 的3×3子矩阵：
```
4 3 8 9 5 1 2 7 6
```
- 数字检查：包含1-9各一次
- 行和检查：
  - 第0行：4+3+8=15
  - 第1行：9+5+1=15
  - 第2行：2+7+6=15
- 列和检查：
  - 第0列：4+9+2=15
  - 第1列：3+5+7=15
  - 第2列：8+1+6=15
- 对角线检查：
  - 主对角线：4+5+6=15
  - 副对角线：8+5+2=15
结果：1个幻方

测试用例

publicclassMain{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[][]grid1={{4,3,8,4},{9,5,1,9},{2,7,6,2}};System.out.println("Test 1: "+solution.numMagicSquaresInside(grid1));// 1// 测试用例2：无幻方int[][]grid2={{8}};System.out.println("Test 2: "+solution.numMagicSquaresInside(grid2));// 0// 测试用例3：多个幻方int[][]grid3={{4,3,8,4,3,8},{9,5,1,9,5,1},{2,7,6,2,7,6}};System.out.println("Test 3: "+solution.numMagicSquaresInside(grid3));// 2// 测试用例4：包含无效数字int[][]grid4={{10,3,8},{9,5,1},{2,7,6}};System.out.println("Test 4: "+solution.numMagicSquaresInside(grid4));// 0// 测试用例5：重复数字int[][]grid5={{4,3,8},{9,5,1},{2,7,7}};System.out.println("Test 5: "+solution.numMagicSquaresInside(grid5));// 0// 测试用例6：中心不是5int[][]grid6={{4,3,8},{9,4,1},{2,7,6}};System.out.println("Test 6: "+solution.numMagicSquaresInside(grid6));// 0// 测试用例7：正确的幻方位置不同int[][]grid7={{0,0,0,0,0},{0,4,3,8,0},{0,9,5,1,0},{0,2,7,6,0},{0,0,0,0,0}};System.out.println("Test 7: "+solution.numMagicSquaresInside(grid7));// 1// 测试用例8：边界情况 - 最小矩阵int[][]grid8={{4,3,8},{9,5,1},{2,7,6}};System.out.println("Test 8: "+solution.numMagicSquaresInside(grid8));// 1// 测试用例9：旋转的幻方int[][]grid9={{2,9,4},{7,5,3},{6,1,8}};System.out.println("Test 9: "+solution.numMagicSquaresInside(grid9));// 1}}