20190830模拟赛 幻方

发表于 更新于 分类于

$Problem’s \ Website$

幻方

$Problem’s \ Description$

给一个$n \times n$的矩阵，将其中的数任意摆放，使其每行、每列、两条对角线所有数之和相等。

$Solution$

首先我们要确定那个相等的和是多少，还是比较好算的，即$lim = tot \div n,\ tot=\sum\limits_{i=1}^{n\times n}{a[i]}$。

因为$n$不是$3$就是$4$，所以我们可以暴力枚举一遍，找出可以拼凑成$lim$的数，用一个变量记录次数，然后按照次数进行降序排序。

最后我们进行$dfs$，下面说一下怎样剪枝

首先明确，我们是一行一行的搜，即对于$x$，先把$y$搜完。

如果一行搜完，这一行的和不为$lim$，再见。

如果当前位置处于对角线，那么要求次数$> 3$，否则，再见。

在倒数第二行时，判断最后一行是否可以使当前的列之和为$lim$，否则，再见。

最后，温馨提示：写搜索时一定要思路清晰，否则后果不堪设想。。。

$Code$

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
109
110
111
112
113
114
115
116
117
118
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define re register
typedef long long ll;
const int Maxn = 10;
struct MAP {
    ll val;
    int times;
    bool operator < (const MAP &x) const {
        return times > x.times;
    }
}a[Maxn * Maxn];
int n;
ll lim;
ll sumx[Maxn], sumy[Maxn], s[Maxn][Maxn];
bool vis[Maxn * Maxn];
inline void D_F() {
    if(n == 4) {
        for(re int i = 1; i <= n * n; ++i)
            for(re int j = i + 1; j <= n * n; ++j)
                for(re int k = j + 1; k <= n * n; ++k)
                    for(re int l = k + 1; l <= n * n; ++l) {
                        if(a[i].val + a[j].val + a[k].val + a[l].val == lim)
                            ++a[i].times, ++a[j].times, ++a[k].times, ++a[l].times;
                    }
    }
    else {
        for(re int i = 1; i <= n * n; ++i)
            for(re int j = i + 1; j <= n * n; ++j)
                for(re int k = j + 1; k <= n * n; ++k) {
                    if(a[i].val + a[j].val + a[k].val == lim)
                        ++a[i].times, ++a[j].times, ++a[k].times;
                }
    }
}
inline bool check(int y) {
    for(re int i = 1; i <= n * n; ++i) {
        if(sumy[y] + a[i].val == lim && !vis[i])
            return 0;
    }
    return 1;
}
inline void dfs(int x, int y) {
//	std :: cerr << x << " " << y << '\n';
    if(y > n) {
        if(sumx[x] != lim)
            return;
        dfs(x + 1, 1);
        return;
    }
    if(x > n) {
        ll sum1 = 0, sum2 = 0;
        for(re int i = 1; i <= n; ++i)
            sum1 += s[i][n - i + 1], sum2 += s[i][i];
        if(sum1 == sum2 && sum1 == lim) {
            for(re int i = 1; i <= n; ++i) {
                for(re int j = 1; j <= n; ++j)
                    printf("%lld ", s[i][j]);
                putchar('\n');
            }
            exit(0);
        }
        return;
    }
    for(re int i = 1; i <= n * n; ++i) {
        if(vis[i])
            continue;
        if(x == n) {
            if(sumy[y] + a[i].val == lim) {
                s[x][y] = a[i].val;
                if((x == n - y + 1 || x == y) && a[i].times < 3)
                    continue;
                sumx[x] += a[i].val;
                sumy[y] += a[i].val;
                vis[i] = 1;
                dfs(x, y + 1);
                sumx[x] -= a[i].val;
                sumy[y] -= a[i].val;
                vis[i] = 0;
            }
        }
        else {
            s[x][y] = a[i].val;
            if((x == n - y + 1 || x == y) && a[i].times < 3)
                continue;
            sumx[x] += a[i].val;
            sumy[y] += a[i].val;
            if(x == n - 1 && check(y)) {
            	sumx[x] -= a[i].val;
            	sumy[y] -= a[i].val;
            	continue;
			}
            vis[i] = 1;
            dfs(x, y + 1);
            sumx[x] -= a[i].val;
            sumy[y] -= a[i].val;
            vis[i] = 0;
        }
    }
}
int main() {
//	freopen("magicsquare.in", "r", stdin);
//	freopen("magicsquare.out", "w", stdout);
    scanf("%d", &n);
    for(re int i = 1; i <= n * n; ++i) {
        scanf("%lld", &a[i].val);
        lim += a[i].val;
    }
    lim /= n;
    D_F();
    std :: sort(a + 1, a + n * n + 1);
//    std :: cerr << lim;
    dfs(1, 1);  
    return 0;
}

$rp++$