题解 P4205 【[NOI2005]智慧珠游戏】

囧仙 · 2020-05-26 23:49:58 · 题解

题目大意

用12种智慧珠组成的零件，填充10\times 10的三角形空白。

题解

楼上的代码都好长呀……这里提供一个非常简短的做法。既可大大减少码量，又可减少因为写错代码而导致的巨大的时间浪费。

虽然智慧珠形态迥异，但我们能够发现，每一个零件都是联通的（废话）。因而，假如我们随便取了零件的某个珠子，可以通过这个珠子上下左右移动，来还原出整个零件。

比如\textbf{零件H}：

假如我们取左上角的点作为起始点，用\tt "URDL"分别表示上、右、下、左，那么这个零件就可以非常简单地表示为\tt"DRUR"。特别地，我们可以任取起始点，因为无论取哪个点，最终都能还原出整个零件，结果相同。

但我们可能遇到类似\textbf{零件J}的困难：

我们无法避免经过重复的格子。这使得我们需要进行去重操作。事实上，可以引入一个新的指令\verb!'<'!，表示回到上一个位置。那么，如果我们取左侧的点作为起始点，\textbf{零件J}就能够表示为\verb!"RU<D<R"!。不重复之前经过的点，就可以避免去重这个问题了。

通过这种方式处理十二个零件，就可以大大减少码量。我们设起始点坐标为(0,0)，根据上述描述的指令进行遍历，就能求出每个零件。选取左上角，计算出剩余部分的相对坐标。

接着我们还需要处理一个棘手的问题：零件可以旋转，翻转。

事实上，这个问题可以很容易地解决。假如，我们将上看成右，右看成下，下看成左，左看成上，重新进行构造，就相当于进行了90\degree旋转，同理可以旋转180\degree,270\degree；翻转只要将上下颠倒就行了，即将上看成下，下看成上。有些零件并不需要处理过多的旋转、翻转操作。我们可以用常量数组存储需要进行哪些操作。

处理完存储12个零件的问题，剩下来的事情就是暴力搜索了。我们从上到下，从左到右考虑每个格子。枚举这个格子选择哪个零件，并进行深搜。之所以上文要以左上角作为参考点，就是为了防止填充的零件影响到之前搜索的点。如果需要影响到前面的点，那么前面的点就需要考虑不填充零件这一种特殊情况，无疑大大增加了枚举的复杂度。

此外，使用指针等方式，还可以进一步缩小码量。最终，这一道码农题就成功被我们用2\rm kB左右的代码写完了。

参考代码

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=l;i>=r;i--)
#define mkp(x,y) make_pair(x,y)
using namespace std;
typedef unsigned long long u64;
const int INF =2147483647;
const int N =10+3,S=8+3,M=64+3;
const char P[][S]={"","AB","BBB","ABB","ABC","CCBB","BC<BB",
                     "ABBC","CBAB","BBCB","BA<C<B","CBCB","ABBB"};
const int Q[]={0,3,1,7,0,3,7,3,7,7,0,3,7};
const int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int X[M],Y[M],tot,B[N][N]; bool flg,V[N];
int W[N][N][S][2],num,T[N][S];
void iit(){
    int x,y,tx,ty,(*w)[2],d,t,o,ox,oy;
    up(1,12,i) up(0,Q[i],j){
        x=y=tx=ty=0,w=W[i][j],t=1,o=(j>3?-1:1);
        for(const char *p=P[i];*p;++p){
            if(*p=='<') x=ox,y=oy; else
            d=(*p+j)&3,ox=x,oy=y,x+=dir[d][0]*o,y+=dir[d][1];
            w[++t][0]=x,w[t][1]=y;
            if(x<=tx) ty=(x<tx?y:min(y,ty)),tx=x;
        }
        up(1,t,k) w[k][0]-=tx,w[k][1]-=ty; T[i][j]=t;
    }
}
int _;
void dfs(int u){
    if((++_)>5e6){puts("No solution"),exit(0);}
    int x=X[u],y=Y[u];  if(B[x][y]) dfs(u+1); else
    up(1,12,i) if(!V[i]) up(0,Q[i],j){
        bool flg=1; int (*w)[2]=W[i][j],t=T[i][j];
        up(1,t,k){
            int nx=x+w[k][0],ny=y+w[k][1];
            if(nx>9||ny<0||ny>nx||B[nx][ny]){flg=0;break;}
        }
        if(!flg) continue;
        up(1,t,k) B[w[k][0]+x][w[k][1]+y]=i;
        ++num,V[i]=true; if(num==12){
            up(0,9,a) up(0,a+1,b) putchar(b==a+1?'\n':'A'+B[a][b]-1);
            exit(0);
        } else dfs(u+1),--num,V[i]=false;
        up(1,t,k) B[w[k][0]+x][w[k][1]+y]=0;
    }
}
char readc(){
    char c; while(!isalpha(c=getchar())&&c!='.'); return c;
}
int main(){
    iit(); up(0,9,i) up(0,i,j){
        char t=readc(); if(t!='.') B[i][j]=t-'A'+1,V[t-'A'+1]=true;
        X[++tot]=i,Y[tot]=j;
    }
    up(1,12,i) if(V[i]) ++num; dfs(1); puts("No solution");
    return 0;
}