自动搬运

查看原文

来自洛谷，原作者为

	wzmzmhk AFO

搬运于2025-08-24 21:24:44，当前版本为作者最后更新于2021-07-29 09:47:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P1406 题解

$upd$ $on$ $2010-10-03:$ 修改了return 的书写错误。

• 题目传送门
• 博客食用效果更佳

思路：

1. 首先可以确定，每行、每列、每个对角线的值 $sum=$ 矩阵中所有元素之和除以 $n$。
2. 因为题目要求按字典序输出，所以先把数组从小到大排序（这一点一定要注意！题目中给出的第三个图片是错误的，没有按照字典序）。
3. 从第一个数进行深度优先搜索，最后输出答案，用exit(0)直接结束程序（return ;的时间较长，需要一步一步地往回回溯）。

优化：

可以进行剪枝：在每一行结束、每一列结束或每一对角线结束时可以用一个函数judge判断这一行、列或对角线之和是否等于 $sum$。

核心代码：

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;
}