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 <= 101 <= grid[0].length <= 100 <= grid[i][j] <= 15执行用时 :8 ms, 在所有 cpp 提交中击败了51.79%的用户
内存消耗 :9.4 MB, 在所有 cpp 提交中击败了19.05%的用户
int equal(vector<int>& a, vector<int>& b, vector<int>& c) {
//cout << a[0] << a[1] << a[2] << endl;
//cout << b[0] << b[1] << b[2] << endl;
//cout << c[0] << c[1] << c[2] << endl;
unordered_set<int> res;
for (auto& i : a) {
if (i < 1 || i > 9) return 0;
res.insert(i);
}
if (res.size() != 3) return 0;
for (auto& i : b) {
if (i < 1 || i > 9) return 0;
res.insert(i);
}
if (res.size() != 6) return 0;
for (auto& i : c) {
if (i < 1 || i > 9) return 0;
res.insert(i);
}
if (res.size() != 9) return 0;
int sum = a[0] + a[1] + a[2];
if (sum == b[0] + b[1] + b[2] && c[0] + c[1] + c[2] == sum) {//行
if (a[0] + b[0] + c[0] == sum && a[1] + b[1] + c[1]== sum && a[2] + b[2] + c[2]==sum) {//列
if (a[0] + b[1]+c[2] ==sum&&b[1]+ a[2] + c[0] ==sum) //a0+b1+c2 a2+b1+c0
return 1;
else
return 0;
}
else
return 0;
}
else
return 0;
}
int numMagicSquaresInside(vector<vector<int>>& grid) {
if (grid.size() < 3 || grid[0].size() < 3) return 0;
int count = 0;
vector<int> a, b, c;
a.resize(3);
b.resize(3);
c.resize(3);
int len1 = grid.size(), len2 = grid[0].size();//len1=3,len2=4
for (int i = 0; i <= len1 - 3; ++i) {
int j = 0;
while (j <= len2 - 3) {
a[0]=(grid[i][j + 0]);
a[1] = (grid[i][j + 1]);
a[2] = (grid[i][j + 2]);
//cout << j << " ";
b[0] = (grid[i+1][j + 0]);
b[1] = (grid[i+1][j + 1]);
b[2] = (grid[i+1][j + 2]);
//cout << j << " ";
c[0] = (grid[i + 2][j + 0]);
c[1] = (grid[i + 2][j + 1]);
c[2] = (grid[i + 2][j + 2]);
//cout << j << " " << endl;
count += equal(a, b, c);
j++;
//cout << j << " ";
//cout << endl << "count " << count<<endl;
}
//cout << endl;
}
return count;
}执行用时 :8 ms, 在所有 cpp 提交中击败了51.79%的用户
内存消耗 :8.9 MB, 在所有 cpp 提交中击败了78.57%的用户
中心点必须是5，且每行每列都需要是15才可以
int equal(vector<int>& a, vector<int>& b, vector<int>& c) {
//cout << a[0] << a[1] << a[2] << endl;
//cout << b[0] << b[1] << b[2] << endl;
//cout << c[0] << c[1] << c[2] << endl;
unordered_set<int> res;
for (auto& i : a) {
if (i < 1 || i > 9) return 0;
res.insert(i);
}
if (res.size() != 3) return 0;
for (auto& i : b) {
if (i < 1 || i > 9) return 0;
res.insert(i);
}
if (res.size() != 6) return 0;
for (auto& i : c) {
if (i < 1 || i > 9) return 0;
res.insert(i);
}
if (res.size() != 9) return 0;
int sum = a[0] + a[1] + a[2]; //sum其实必须是15才可以
if (sum == b[0] + b[1] + b[2] && c[0] + c[1] + c[2] == sum) {//行
if (a[0] + b[0] + c[0] == sum && a[1] + b[1] + c[1]== sum && a[2] + b[2] + c[2]==sum) {//列
if (a[0] + b[1]+c[2] ==sum&&b[1]+ a[2] + c[0] ==sum) //a0+b1+c2 a2+b1+c0
return 1;
else
return 0;
}
else
return 0;
}
else
return 0;
}
int numMagicSquaresInside(vector<vector<int>>& grid) {
if (grid.size() < 3 || grid[0].size() < 3) return 0;
int count = 0;
vector<int> a, b, c;
a.resize(3);
b.resize(3);
c.resize(3);
int len1 = grid.size(), len2 = grid[0].size();//len1=3,len2=4
for (int i = 0; i <= len1 - 3; ++i) {
int j = 0;
while (j <= len2 - 3) {
if (grid[i + 1][j + 1] != 5) {
j++;
continue;
}
a[0]=(grid[i][j + 0]);
a[1] = (grid[i][j + 1]);
a[2] = (grid[i][j + 2]);
//cout << j << " ";
b[0] = (grid[i+1][j + 0]);
b[1] = (grid[i+1][j + 1]);
b[2] = (grid[i+1][j + 2]);
//cout << j << " ";
c[0] = (grid[i + 2][j + 0]);
c[1] = (grid[i + 2][j + 1]);
c[2] = (grid[i + 2][j + 2]);
//cout << j << " " << endl;
count += equal(a, b, c);
j++;
//cout << j << " ";
//cout << endl << "count " << count<<endl;
}
//cout << endl;
}
return count;
}