题目166：十字形
Criss CrossA 4x4 grid is filled with digits d, 0 ≤ d ≤ 9.
It can be seen that in the grid
6 3 3 0
5 0 4 3
0 7 1 4
1 2 4 5
the sum of each row and each column has the value 12. Moreover the sum of each diagonal is also 12.
In how many ways can you fill a 4x4 grid with the digits d, 0 ≤ d ≤ 9 so that each row, each column, and both diagonals have the same sum?
题目：
一个 4×4 的网格用数字 d 填充，0 ≤ d ≤ 9。
可以看出，在下面这个网格中：
6 3 3 0
5 0 4 3
0 7 1 4
1 2 4 5
每一行和每一列的和都是 12，此外对角线之和也是 12。
那么，你能以多少种方法用 0-9 的数字填充一个 4×4 的网格，使得每行、每列和对角线的和相等呢？
应用穷举搜索。
答案：7130034
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
#include <omp.h>
using namespace std;
struct stMatrix//4x4矩阵
{
unsigned char a;
stMatrix(void)
{
memset(a, 0, sizeof(a));
}
bool check(int d)//验证对角线与反对角线元素之和是否满足要求
{
if (int(a + a + a + a) != d)
return false;
if (int(a + a + a + a) != d)
return false;
return true;
}
};
inline void getrow(int d, int n, vector<short>& vRows) //生成所有满足条件的行
{
int s = 0, k = n;
while (k > 0)
{
s += k % 10;
k /= 10;
}
if (s == d)
vRows.push_back(n);
}
long long cml(stMatrix m)//将矩阵变成long long以便查重
{
long long x = 0;
for (int r = 3; r >= 0; --r)
{
for (int c = 3; c >= 0; --c)
x = x * 10 + m.a;
}
return x;
}
void gm1(stMatrix m, int d, set<long long>& sM)//检验矩阵是否满足要求并查重
{
if (m.check(d))
{
sM.insert(cml(m));
stMatrix m1;
for (int i = 0; i < 4; ++i)
{
for (int j = 0; j < 4; ++j)
m1.a = m.a;
}
sM.insert(cml(m1));
for (int i = 0; i < 4; ++i)
{
for (int j = 0; j < 4; ++j)
m1.a = m.a;
}
sM.insert(cml(m1));
for (int i = 0; i < 4; ++i)
{
for (int j = 0; j < 4; ++j)
m1.a = m.a;
}
sM.insert(cml(m1));
}
}
void gm(const short b, int d, set<long long>& sM)//根据前3行来生成一个矩阵
{
stMatrix m;
short c;
c = b;
c = b;
c = b;
short s = 0;
for (int i = 0; i < 4; ++i)//生成矩阵
{
m.a = c % 10;
m.a = c % 10;
m.a = c % 10;
m.a = d - (m.a + m.a + m.a);
if (m.a < 0 || m.a>9)
return;
s += m.a;
c /= 10;
c /= 10;
c /= 10;
}
if (s != d)
return;
int x = { 0,1,2,3 };
do //对行进行排列变换
{
stMatrix m1;
for (int i = 0; i < 4; ++i)
{
for (int j = 0; j < 4; ++j)
m1.a = m.a];
}
int y = { 0,1,2,3 };
do //对列进行排列变换
{
stMatrix m2;
for (int i = 0; i < 4; ++i)
{
for (int j = 0; j < 4; ++j)
m2.a = m1.a];
}
gm1(m2, d, sM);//检验并查重
} while (next_permutation(y, y + 4));
} while (next_permutation(x, x + 4));
}
int main(void)
{
long long nCount = 0;
#pragma omp parallel for reduction(+:nCount) schedule(dynamic,1)
for (int d = 0; d <= 18; ++d)//对和值进行枚举
{
vector<short> vRows;
for (short i = 0; i < 10000; ++i)
getrow(d, i, vRows);
set<long long> sM;
for (int i = 0; i < (int)vRows.size(); ++i)
{
short b;
b = vRows;
for (int j = i; j < (int)vRows.size(); ++j)
{
b = vRows;
for (int k = j; k < (int)vRows.size(); ++k)
{
b = vRows;
gm(b, d, sM);
}
}
}
nCount += sM.size();
if (36 - d != d)
nCount += sM.size();//根据对称性
}
cout << nCount << endl;
return 0;
}
页:
[1]