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 <= 101 <= grid[0].length <= 100 <= grid[i][j] <= 15
第一版，没意思，纯暴力法，就是比较麻烦
执行用时 :8 ms, 在所有 cpp 提交中击败了51.79%的用户
内存消耗 :9.4 MB, 在所有 cpp 提交中击败了19.05%的用户
intequal(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) return0;
res.insert(i);
}
if (res.size() !=3) return0;
for (auto&i : b) {
if (i<1||i>9) return0;
res.insert(i);
}
if (res.size() !=6) return0;
for (auto&i : c) {
if (i<1||i>9) return0;
res.insert(i);
}
if (res.size() !=9) return0;
intsum=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
return1;
else
return0;
}
else
return0;
}
else
return0;
}
intnumMagicSquaresInside(vector<vector<int>>&grid) {
if (grid.size() <3||grid[0].size() <3) return0;
intcount=0;
vector<int>a, b, c;
a.resize(3);
b.resize(3);
c.resize(3);
intlen1=grid.size(), len2=grid[0].size();//len1=3,len2=4
for (inti=0; i<=len1-3; ++i) {
intj=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;
}
returncount;
}
第二版，经过提示，改进一点
执行用时 :8 ms, 在所有 cpp 提交中击败了51.79%的用户
内存消耗 :8.9 MB, 在所有 cpp 提交中击败了78.57%的用户
中心点必须是5，且每行每列都需要是15才可以
intequal(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) return0;
res.insert(i);
}
if (res.size() !=3) return0;
for (auto&i : b) {
if (i<1||i>9) return0;
res.insert(i);
}
if (res.size() !=6) return0;
for (auto&i : c) {
if (i<1||i>9) return0;
res.insert(i);
}
if (res.size() !=9) return0;
intsum=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
return1;
else
return0;
}
else
return0;
}
else
return0;
}
intnumMagicSquaresInside(vector<vector<int>>&grid) {
if (grid.size() <3||grid[0].size() <3) return0;
intcount=0;
vector<int>a, b, c;
a.resize(3);
b.resize(3);
c.resize(3);
intlen1=grid.size(), len2=grid[0].size();//len1=3,len2=4
for (inti=0; i<=len1-3; ++i) {
intj=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;
}
returncount;
}
