leetcode 840. 矩阵中的幻方

矩阵中的幻方"/>

leetcode 840. 矩阵中的幻方

【题目】840. 矩阵中的幻方

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=

【解题思路1】按定义

可以在代码中添加 if grid[r+1][c+1] != 5: continue，帮助我们略过一些循环：

• 网格的总和是 45，因为网格必须是 1 到 9 不同的数字。
• 每一列和行加起来必须是 15，乘以 3 则是网格的总和。
• 对角线的和也必须是 15，题目中说了对角线与列，行的和相同。
• 将四条穿过中心的线的 12 个值相加（即一行一列两条对角线），这四条线加起来等于 60；而整个网
• 格加起来为 45。则中心等于 （60-45）/3 = 5

class Solution {public int numMagicSquaresInside(int[][] grid) {int R = grid.length, C = grid[0].length;int ans = 0;for (int r = 0; r < R-2; ++r)for (int c = 0; c < C-2; ++c) {if (grid[r+1][c+1] != 5) continue;if (magic(grid[r][c], grid[r][c+1], grid[r][c+2],grid[r+1][c], grid[r+1][c+1], grid[r+1][c+2],grid[r+2][c], grid[r+2][c+1], grid[r+2][c+2]))ans++;}return ans;}public boolean magic(int... vals) {int[] count = new int[16];for (int v: vals) count[v]++;for (int v = 1; v <= 9; ++v)if (count[v] != 1)return false;return (vals[0] + vals[1] + vals[2] == 15 &&vals[3] + vals[4] + vals[5] == 15 &&vals[6] + vals[7] + vals[8] == 15 &&vals[0] + vals[3] + vals[6] == 15 &&vals[1] + vals[4] + vals[7] == 15 &&vals[2] + vals[5] + vals[8] == 15 &&vals[0] + vals[4] + vals[8] == 15 &&vals[2] + vals[4] + vals[6] == 15);}
}

【解题思路2】抽屉算法

另一种分析
满足幻方的条件必定是中间的数字为5,周围的数字为满足 1->6->7->2->9->4->3->8->1
的这种圆环结构,5的上下左右必定是 1、9、3、7(这四个数字都只能组成两组 15)
并且5的周围的数字其实都可以跳过,这里没作实现
1.利用数组的索引语义记录索引对应的下一个数字
2.若5的下一个值满足条件,且该值的下一行对应列满足条件,顺时针
若5的下一个值满足条件,且该值的上一行对应列满足条件,逆时针
3.总共判断6次即可(前两次已经判断过了)

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;       }
}