【题解】P2927

· · 题解

题目

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

我们只要先将输入的数据按字母表顺序排序一遍，然后再跑一遍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。