870 Magic Squares In Grid
870 Magic Squares In Grid
Magic Squares In Grid 
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 a row x col grid of integers, how many 3 x 3 magic square subgrids are there?
Note: while a magic square can only contain numbers from 1 to 9, grid may contain numbers up to 15.
Example 1:
1
2
3
4
5
6
7
8
9
10
**Input:** grid = [[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:
while this one is not:
In total, there is only one magic square inside the given grid.
Example 2:
1
2
3
4
**Input:** grid = [[8]]
**Output:** 0
Constraints:
1
2
3
4
row == grid.length
col == grid[i].length
1 <= row, col <= 10
0 <= grid[i][j] <= 15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
use std::collections::HashSet;
impl Solution {
pub fn num_magic_squares_inside(grid: Vec<Vec<i32>>) -> i32 {
fn is_magic_square(g: Vec<Vec<i32>>) -> bool {
//print!("{:?}", g);
let mut a = 0;
for k in g.clone() {
let mut s = 0;
for m in k {
s += m
}
if a == 0 {
a = s
} else {
if (a != s) {
return false
}
}
}
if a != g[0][0] + g[1][1] + g[2][2] {
return false;
}
if a != g[0][2] + g[1][1] + g[2][0] {
return false;
}
if a != g[0][0] + g[1][0] + g[2][0] {
return false;
}
if a != g[0][1] + g[1][1] + g[2][1] {
return false;
}
if a != g[0][2] + g[1][2] + g[2][2] {
return false;
}
let mut hs = HashSet::new();
hs.insert(g[0][0]);
hs.insert(g[0][1]);
hs.insert(g[0][2]);
hs.insert(g[1][0]);
hs.insert(g[1][1]);
hs.insert(g[1][2]);
hs.insert(g[2][0]);
hs.insert(g[2][1]);
hs.insert(g[2][2]);
if hs.len() != 9 {
return false;
}
if hs.contains(&0) {
return false;
}
if g[0][0] + g[0][1] + g[0][2] + g[1][0] + g[1][1] + g[1][2] + g[2][0] + g[2][1] + g[2][2] != 45 {
return false;
}
return true;
}
let mut i = 0;
let mut j = 0;
let mut ans = 0;
for i in 0..grid.len() {
let mut d = i;
for j in 0..grid[i].len() {
let mut m = Vec::new();
while(d < i + 3) {
let mut n = Vec::new();
if j + 2 < grid[i].len() && d < grid.len() {
n.push(grid[d][j]);
n.push(grid[d][j+1]);
n.push(grid[d][j+2]);
} else {
break
}
d += 1;
m.push(n.clone());
//print!("{:?} nnnnn", m);
}
if m.len() == 3 && is_magic_square(m.clone()) {
ans += 1;
}
d = i;
}
}
return ans;
}
}
This post is licensed under CC BY 4.0 by the author.