# C#LeetCode刷题之#840-矩阵中的幻方（Magic Squares In Grid）

3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。

[9,5,1,9],
[2,7,6,2]]

438
951
276

384
519
762

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
276

while this one is not:
384
519
762

In 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);

}

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

}```

```1
0```