自动搬运

查看原文

来自洛谷，原作者为

	Utilokasteinn 技不如人

搬运于2025-08-24 21:23:13，当前版本为作者最后更新于2020-08-11 11:41:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P1274 魔术数字游戏

一道深搜回溯题，过程代码判断的代码挺多的。

先说一下思路，从$a_{1,1}$开始深搜，然后到$a_{1,2}$，到$a_{1,3}$，到$a_{1,4}$。到了每行的最后一个数时就来到下一行，即$a_{2,1}$。

搜到$a_{5,1}$的时候就开始判断，（注意不是$a_{4,4}$，因为只有到$a_{5,1}$的时候$a_{4,4}$才有值。）如果判断全部符合要求就输出，否则就回溯重搜。

但是这样会超时，比如说，第一行的四个数分别是

这样肯定不符合要求，但是这个时候却要继续往下搜，这样就浪费了不少时间。

所以我们可以在每次深搜的时候就判断一次，如果不符合条件就这就$return$，这样就可以节省不少时间。

我们可以发现，如果每次深搜时都判断一次，而每次判断虽然时间复杂度是$O(1)$，（应该是吧，我不太清楚）但是常数巨大。

由于$a_{4,4}$是在最后一次深搜时才出现值的，所以之前可以不用判断一下四个需要用到$a_{4,4}$值的判断：

• 四个角落上的数字和。

• 右下$2\times 2$的数字和。

• 第四行的数字和。

• 第四列的数字和。

• 左上到右下对角线的数字和。

所以，我们可以在之前的判断少一上这$5$个判断，然后再写一个新的判断，包含这$5$个判断，这样常数就会大幅度减少，速度变快。

由于这题输出量较大，建议用$printf$，如果可以手写快输（快写）也是可以的，当然$fwrite$也可以。

附上我的垃圾快输（快写）（可能会出锅，我这题没试过）：

inline void write(int x)
{
    static char buf[15];
    static int len=-1;
    if(x<0)putchar('-'),x=-x;
    do buf[++len]=x%10,x/=10;while(x);
    while(len>=0)putchar(buf[len--]+'0');
}

附上完整的有详细注释的代码：

#include<bits/stdc++.h>
using namespace std;
int a[5][5],v[17],n,m;
//a[i][j]来记录位置[i,j]所存的数，v[i]存i是否用过，n和m如题 
int check(int x,int y)
{ 
	//这里不要把两个if改为一个，否则全错 
	//前一个if是判断要判断的数是否在那个范围以内
	//后一个if是看和是不是34，如果一个不是就直接返回0，说明该方案不行，需要回溯重搜 
	if(x>2||x==2&&y>=2)
		if(a[1][1]+a[1][2]+a[2][1]+a[2][2]!=34)return 0;//左上角2*2位置的数的和 
	if(x>2||x==2&&y==4)
		if(a[1][3]+a[1][4]+a[2][3]+a[2][4]!=34)return 0;//右上角2*2位置的数的和 
	if(x==4&&y>=2)
		if(a[3][1]+a[3][2]+a[4][1]+a[4][2]!=34)return 0;//左下角2*2位置的数的和 
	if(x>3||x==3&&y>=3)
		if(a[2][2]+a[2][3]+a[3][2]+a[3][3]!=34)return 0;//中央的2*2位置的数的和 
	if(x>1||x==1&&y>=4)
		if(a[1][1]+a[1][2]+a[1][3]+a[1][4]!=34)return 0;//第一行所有数的和 
	if(x>2||x==2&&y>=4)
		if(a[2][1]+a[2][2]+a[2][3]+a[2][4]!=34)return 0;//第二行所有数的和 
	if(x>3||x==3&&y>=4)
		if(a[3][1]+a[3][2]+a[3][3]+a[3][4]!=34)return 0;//第三行所有数的和 
	if(x==4&&y>=1)
		if(a[1][1]+a[2][1]+a[3][1]+a[4][1]!=34)return 0;//第一列所有数的和 
	if(x==4&&y>=2)
		if(a[2][1]+a[2][2]+a[2][3]+a[2][4]!=34)return 0;//第二列所有数的和 
	if(x==4&&y>=3)
		if(a[3][1]+a[3][2]+a[3][3]+a[3][4]!=34)return 0;//第三列所有数的和 
	if(x==4&&y>=1)
		if(a[1][4]+a[2][3]+a[3][2]+a[4][1]!=34)return 0;//左下到右上对角线所有数的和 
	return 1;
} 
int check1()//搜完了，所有位置肯定都有数了，所以不必传参数x，y 
{
	if(a[1][1]+a[1][4]+a[4][1]+a[4][4]!=34)return 0;//四个角的数的和 
	if(a[3][3]+a[3][4]+a[4][3]+a[4][4]!=34)return 0;//右下角2*2位置的数的和 
	if(a[4][1]+a[4][2]+a[4][3]+a[4][4]!=34)return 0;//第四行所有数的和 
	if(a[1][4]+a[2][4]+a[3][4]+a[4][4]!=34)return 0;//第四列所有数的和 
	if(a[1][1]+a[2][2]+a[3][3]+a[4][4]!=34)return 0;//左上到右下对角线所有数的和 
	return 1;//如果所有都满足就返回1 
}
void dfs(int x,int y)
{
	if(x==5&&y==1&&check1())
	{
		for(int i=1;i<=4;i++)//输出 
		{
			for(int j=1;j<=4;j++)
				printf("%d ",a[i][j]);//printf较快 
			putchar('\n');//putchar较快 
		}
		putchar('\n');//还要再换一次行 
		return;//答案输出后就可以返回了 
	}
	if(a[x][y])//如果当前这个位置有数了 
		if(y==4)dfs(x+1,1);//如果到了一行中的最后一个位置，那就到下一行继续搜 
		else dfs(x,y+1);//否则就再往下一个数搜
	else//如果没有数 
	{
		if(y==1)x--,y=4;//如果是一行的第一个位置，就返回到上一行的最后一个位置搜 
		else y--;//否则就退到前一个位置 
		if(!check(x,y))return;//如果不符合，就可以直接return了 
		if(y==4)x++,y=1;//如果是一行中最后一个数，就来到下一行第一个数 
		else y++;//否则就来到下一个位置 
		for(int i=2;i<=16;i++)//继续深搜 
			if(!v[i])//如果当前这个数没有用过 
			{
				v[i]=1;//标记这个数用过了 
				a[x][y]=i;//当前位置的数为 i 
				if(y==4)dfs(x+1,1);//如果到了一行中最后一个位置，就来到下一行 
				else dfs(x,y+1);//否则就来到同一行下一个位置 
				a[x][y]=v[i]=0;//回溯时清零 
			}
	}
}
int main()
{
	cin>>n>>m;//输入n和m 
	a[n][m]=v[1]=1;//a[n][m]的值为1，且标记用过1这个数 
	dfs(1,1);//从第一行第一个数开始搜 
	return 0;//结束 
}

平均速度$2s$左右，应该是非打表（一点也算）中比较快的。（吐槽一下，本题的$rank\;1$是打表过的……）代码也很短，去掉注释$1.73KB$，而且还没有用三目运算符之类的。比

无注释代码我放这里，仅供参考。

谢谢观赏，麻烦点个赞犒劳一下……