
问题
3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。
给定一个由整数组成的 m * n 矩阵,其中有多少个 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 = grid[0].length <= 10
0 <= grid[i][j] <= 15
A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.
Given an grid of integers, how many 3 x 3 “magic square” subgrids are there? (Each subgrid is contiguous).
Input: [[4,3,8,4],
[9,5,1,9],
[2,7,6,2]]Output: 1
Explanation:
The following subgrid is a 3 x 3 magic square:
438
951
276while this one is not:
384
519
762In total, there is only one magic square inside the given grid.
Note:
1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15
示例
public class Program { public static void Main(string[] args) { int[][] nums = null; nums = new int[3][] {new int[]{4,3,8,4}, new int[] {9,5,1,9}, new int[] {2,7,6,2} }; var res = NumMagicSquaresInside(nums); Console.WriteLine(res); nums = new int[3][] {new int[]{1,0,3,8}, new int[] {3,7,2,4}, new int[] {5,8,1,0} }; res = NumMagicSquaresInside2(nums); Console.WriteLine(res); Console.ReadKey(); } private static int NumMagicSquaresInside(int[][] grid) { var num = 0; for(var i = 1; i < grid.Length - 1; i++) { for(var j = 1; j < grid[i].Length - 1; j++) { if(grid[i][j] == 5) { num = IsMagicSquare(grid, i, j) ? ++num : num; } } } return num; } private static bool IsMagicSquare(int[][] grid, int i, int j) { //原始解法,不推荐 //记录每个值,看是不是9位,因为从1-9都必须出现 var dic = new Dictionary<int, int>(); dic[grid[i - 1][j - 1]] = grid[i - 1][j - 1]; dic[grid[i - 1][j]] = grid[i - 1][j]; dic[grid[i - 1][j + 1]] = grid[i - 1][j + 1]; dic[grid[i][j - 1]] = grid[i][j - 1]; dic[grid[i][j]] = grid[i][j]; dic[grid[i][j + 1]] = grid[i][j + 1]; dic[grid[i + 1][j - 1]] = grid[i + 1][j - 1]; dic[grid[i + 1][j]] = grid[i + 1][j]; dic[grid[i + 1][j + 1]] = grid[i + 1][j + 1]; //不为9或不在1-9范围之内,则不是幻方 if(dic.Count != 9) return false; foreach(var item in dic) { if(item.Value > 9 || item.Value < 0) return false; } //记录3行、3列、2对角线 var sum_row1 = grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1]; var sum_row2 = grid[i][j - 1] + grid[i][j] + grid[i][j + 1]; var sum_row3 = grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]; var sum_col1 = grid[i - 1][j - 1] + grid[i][j - 1] + grid[i + 1][j - 1]; var sum_col2 = grid[i - 1][j] + grid[i][j] + grid[i + 1][j]; var sum_col3 = grid[i - 1][j + 1] + grid[i][j + 1] + grid[i + 1][j + 1]; var sum_cross1 = grid[i - 1][j - 1] + grid[i][j] + grid[i + 1][j + 1]; var sum_cross2 = grid[i - 1][j + 1] + grid[i][j] + grid[i + 1][j - 1]; var dic2 = new Dictionary<int, int>(); dic2[sum_row1] = 0; dic2[sum_row2] = 0; dic2[sum_row3] = 0; dic2[sum_col1] = 0; dic2[sum_col2] = 0; dic2[sum_col3] = 0; dic2[sum_cross1] = 0; dic2[sum_cross2] = 0; //看值是不是相同并且值之和为15 return dic2.Count == 1 && sum_row1 == 15; } private static int NumMagicSquaresInside2(int[][] grid) { var num = 0; for(var i = 1; i < grid.Length - 1; i++) { for(var j = 1; j < grid[i].Length - 1; j++) { if(grid[i][j] == 5) { num = IsMagicSquare(grid, i, j) ? ++num : num; } } } return num; } private static bool IsMagicSquare2(int[][] grid, int row, int col) { //值必须是1-9 for(var i = row - 1; i <= row + 1; i++) for(var j = col - 1; j <= col + 1; j++) if(grid[i][j] < 1 || grid[i][j] > 9) return false; //不考虑中间的5,只需要考虑4个位置的值的和为10即可 return !(grid[row - 1][col - 1] + grid[row + 1][col + 1] != 10 || grid[row - 1][col] + grid[row + 1][col] != 10 || grid[row - 1][col + 1] + grid[row + 1][col - 1] != 10 || grid[row][col - 1] + grid[row][col + 1] != 10); } }
以上给出2种算法实现,以下是这个案例的输出结果:
1 0
分析:
显而易见,以上2种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3752。