自动搬运

查看原文

来自洛谷，原作者为

	seac_blue Cogito ergo sum.

搬运于2025-08-24 21:55:03，当前版本为作者最后更新于2021-10-15 09:35:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

主要算法是搜索，注意实现细节。

思路

1. 读入并处理每一块拼图

2. dfs 每一块拼图放在哪里

• 2.1. 判断能否放置

• 2.2. 如果能，将拼图对应的相对坐标覆盖到版面的绝对坐标上

• 2.3. 重复 2.

• 2.4. 回溯，将拼图对应的相对坐标从版面的绝对坐标抠出来

3. 每次 bfs 判断是否覆盖满

• 3.1 开一个答案数组和答案个数记录

• 3.2 如果答案个数 $=0\to$ No solution

• 3.3 如果答案个数 $=1\to$ Yes, only one!

• 3.4 如果答案个数 $=2\to$ Yes, many! 并且直接退出。

实现

步骤 1 使用结构体存储。

步骤 2.1 可以用一一对应的方式写个判断函数。

步骤 2.2 和 2.4 可以写个覆盖函数，参数稍作修改，不需要写两次。

步骤 3 需要写个判断是否填满的函数。

总体框架见上，依旧注意实现细节。

（感觉这题难度标高了，建议绿）

代码

代码省略了头文件和快读。变量和函数都写有一定的注释解释。

using namespace std;
typedef long long ll;

ll read(){/* 快读 */}
ll reads(){/* 读入一个数字 0/1 */}

ll n;
ll f[5][5];// 操作版面
ll restime;// 答案个数
ll res[5][5];// 答案版面
bool allret;// 如果 allret=true 那么 dfs() 全部返回

struct Puzzle{
	ll w,h;
	bool p[5][5];
}a[20];

bool allFill(){// 版面是否填满
	for(ll i=1;i<=4;++i){
		for(ll j=1;j<=4;++j){
			if(!f[i][j])return false;
		}
	}
	return true;
}
bool check(ll id,ll x,ll y){// 是否可以以 (x,y) 为左上角放置拼图 id
	for(ll i=1;i<=a[id].w;++i){
		for(ll j=1;j<=a[id].h;++j){
			if(!a[id].p[i][j])continue;
			ll px=x+i-1,py=y+j-1;
			if(px>4 || py>4)return false;
			if(f[px][py])return false;
		}
	}
	return true;
}
void set(ll id,ll x,ll y,ll fillOper){// 以 (x,y) 为左上角放置 id
	for(ll i=1;i<=a[id].w;++i){
		for(ll j=1;j<=a[id].h;++j){
			if(!a[id].p[i][j])continue;
			ll px=x+i-1,py=y+j-1;
			f[px][py]=fillOper;
		}
	}
}

void dfs(ll k){
	bool p=allFill();
	if(p || k>n){// 边界条件
		if(p){// 版面填满
			if(restime){
				allret=true;
				restime=2;
				return;
			}else{
				restime=1;
				for(ll i=1;i<=4;++i){
					for(ll j=1;j<=4;++j){
						res[i][j]=f[i][j];
					}
				}
				return;
			}
		}
		return;
	}
	for(ll i=1;i<=4;++i){
		for(ll j=1;j<=4;++j){
			if(check(k,i,j)){
				set(k,i,j,k);
				dfs(k+1);
				if(allret)return;
				set(k,i,j,0);
			}
		}
	}
	dfs(k+1);// 选择不要这块拼图，但是似乎所有拼图都会用上……？
}

int main(){
	while(scanf("%lld\n",&n)!=EOF){
		for(ll i=1;i<=n;++i){
			a[i].w=read();a[i].h=read();
			for(ll j=1;j<=a[i].w;++j){
				for(ll k=1;k<=a[i].h;++k){
					a[i].p[j][k]=reads();
				}
			}
		}
		allret=false;restime=0;
		for(ll i=1;i<=4;++i){
			for(ll j=1;j<=4;++j){
				f[i][j]=0;
			}
		}
		dfs(1);
		if(restime==2){
			printf("Yes, many!\n");
		}if(restime==0){
			printf("No solution\n");
		}if(restime==1){
			printf("Yes, only one!\n");
			for(ll i=1;i<=4;++i,putchar('\n')){
				for(ll j=1;j<=4;++j){
					printf("%lld",res[i][j]);
				}
			}
		}
	}
	return 0;
}