自动搬运

查看原文

来自洛谷，原作者为

	do_while_false **

搬运于2025-08-24 21:43:31，当前版本为作者最后更新于2020-03-12 09:24:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目

此题可以直接用暴力搜索过，但注意代码里有许多细节，要注意，代码还是比较长的，要注意细节。

我们只要先将输入的数据按字母表顺序排序一遍，然后再跑一遍dfs即可，具体的说明都在代码里。

代码如下：

#include<bits/stdc++.h>//万能头 
#define MAXN 100 + 10 //数组的最大范围 
using namespace std;//标准命名空间 
int n,m,ans,visit[MAXN],id[MAXN][MAXN],v[MAXN][MAXN],sum[MAXN][MAXN],f[MAXN][MAXN];
int fx[5]={0,-1,0,1,0},fy[5]={0,0,1,0,-1},which[5]={0,3,4,1,2};//用于dfs的方向数组 
char s[10];//用于输入 
struct node {
	int x;
	char c[5][5];
}a[MAXN];//用于储存 
bool cmp(node x,node y) {//比较函数 
	return x.x<y.x;
}
inline int read() {//快读 
	int r=0;bool flag=true;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') flag=false;ch=getchar();}
	while(ch>='0'&&ch<='9'){r=(r<<3)+(r<<1)+(ch^48);ch=getchar();}
	return flag==true?r:~r+1;
}
void dfs(int x,int y) {//暴力搜索 
	if(ans) return;//边界条件 
	if(x==n+1&&y==1) {//边界条件2 
		if(ans==0) {//边界条件3
			for(int i=1;i<=n;i++)
				for(int j=1;j<=m;j++)
					sum[i][j]=id[i][j],f[i][j]=v[i][j];
			ans=1;//使其不满足条件，退出循环 
		}
		return;
	}
	int xx,yy,nx,ny;
	if(y+1<=m) nx=x,ny=y+1;//初始化
	else nx=x+1,ny=1;//初始化
	bool bk;
	for(int i=1;i<=n*m;i++) {
		if(visit[i]) continue;//访问过了，进入下一次循环 
		for(int j=1;j<=4;j++) {
			bk=1;//初始化 
			for(int k=1;k<=4;k++) {
				xx=x+fx[k];//下一轮搜索的下标 
				yy=y+fy[k];//下一轮搜索的下标 
				if(xx>=1&&yy>=1&&xx<=n&&yy<=m) {//判断是否越界 
					int o=id[xx][yy],q=v[xx][yy];//下一轮搜索的值 
					if(o&&q&&a[i].c[j][k]!=a[o].c[q]//判断是否可以拼在一起[which[k]]) {
						bk=0;break;//退出循环 
					}
				}
				else if(a[i].c[j][k]!='0') {//否则就直接返回 
					bk=0;break;//退出循环 
				}
			}
			if(bk) {//符合条件，继续搜索 
				id[x][y]=i;v[x][y]=j;visit[i]=1;//标记访问 
				dfs(nx,ny);//继续搜索 
				id[x][y]=0;v[x][y]=0;visit[i]=0;//回溯 
			}
		}
	}	
}

int main(void) {
	n=read();m=read();//输入 
	for(int i=1;i<=n*m;i++) {
		a[i].x=read();//输入 
		for(int j=1;j<=4;j++) {
			scanf("%s",s);//输入 
			a[i].c[1][j]=s[0];//赋值 
		}
		for(int j=2;j<=4;j++)
			for(int k=1;k<=4;k++) 
				a[i].c[j][k]=a[i].c[j-1][(k-1==0)?4:k-1];//储存 
	}
	sort(a+1,a+1+n*m,cmp);//排序 
	memset(v,0,sizeof(v));//初始化 
	memset(id,0,sizeof(id));//初始化 
	memset(visit,0,sizeof(visit));//初始化 
	ans=0;//初始化 
	dfs(1,1);//开始搜索 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) {
			printf("%d ",a[sum[i][j]].x);//输出答案 
			for(int k=1;k<=4;k++) {
				printf("%c ",a[sum[i][j]].c[f[i][j]][k]);//输出答案 
			}
			printf("\n");//输出答案 
		}
	return 0;
}

管理员求过，QWQ。