P1406 题解
wzmzmhk
·
·
题解
P1406 题解
- **[题目传送门](https://www.luogu.com.cn/problem/P1406)**
- **[博客食用效果更佳](https://www.luogu.com.cn/blog/wzmzmhk/solution-p1406#)**
------------
**思路：**
1. 首先可以确定，每行、每列、每个对角线的值 $sum=$ 矩阵中所有元素之和除以 $n$。
1. 因为题目要求按字典序输出，所以先把数组从小到大排序（这一点一定要注意！题目中给出的第三个图片是错误的，没有按照字典序）。
1. 从第一个数进行深度优先搜索，最后输出答案，用```exit(0)```直接结束程序（```return ;```的时间较长，需要一步一步地往回回溯）。
**优化：**
可以进行剪枝：在每一行结束、每一列结束或每一对角线结束时可以用一个函数```judge```判断这一行、列或对角线之和是否等于 $sum$。
核心代码：
```cpp
bool judge(int x, int y, int i) {
if (y == n) {
int sum1 = a[i];
for (int j = 1; j < n; j++)
sum1 += ans[x][j];
if (sum1 != sum)
return true;
}//判断每一行
if (x == n) {
int sum1 = a[i];
for (int j = 1; j < n; j++)
sum1 += ans[j][y];
if (sum1 != sum)
return true;
}//判断每一列
if (x == n && y == n) {
int sum1 = a[i];
for (int j = 1; j < n; j++)
sum1 += ans[j][j];
if (sum1 != sum)
return true;
}//判断正对角线
if (x == n && y == 1) {
int sum1 = a[i];
for (int j = 1; j < n; j++)
sum1 += ans[j][n - j + 1];
if (sum1 != sum)
return true;
}//判断负对角线
return false;
}
void dfs(int x, int y) {
if (x == n + 1) {
print();
exit(0);
}//如果搜到了x+1行，说明已经搜索完毕，直接输出。
for (int i = 1; i <= n * n; i++) {
if (t[i] == 0) {
if (judge(x, y, i))//用judge函数进行优化剪枝
continue;
t[i] = 1;//打标记
ans[x][y] = a[i];//将a[i]加入答案中
y != n ? dfs(x, y + 1) : dfs(x + 1, 1);
//三目运算符，相当于：
/*
if(y != n)
dfs(x, y + 1);
else
dfs(x + 1, 1);
*/
t[i] = 0;
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n * n; i++) {
cin >> a[i];
sum += a[i];
}
sum = sum / n;
sort(a + 1, a + 1 + n * n);//为保证输出为字典序，进行排序
dfs(1, 1);
return 0;
}
```