题解 P4205 【[NOI2005]智慧珠游戏】
囧仙
2020-05-26 23:49:58
## 题目大意
用$12$种智慧珠组成的零件,填充$10\times 10$的三角形空白。
## 题解
楼上的代码都好长呀……这里提供一个非常简短的做法。既可大大减少码量,又可减少因为写错代码而导致的巨大的时间浪费。
虽然智慧珠形态迥异,但我们能够发现,每一个零件都是联通的(废话)。因而,假如我们随便取了零件的某个珠子,可以通过这个珠子**上下左右移动**,来还原出整个零件。
比如$\textbf{零件H}$:
$$\begin{matrix}\bigcirc-\kern{-12pt}&\bigcirc-\kern{-12pt}&\bigcirc \cr|&|\cr\bigcirc-\kern{-12pt}&\bigcirc \cr\end{matrix}$$
假如我们取左上角的点作为起始点,用$\tt "URDL"$分别表示上、右、下、左,那么这个零件就可以非常简单地表示为$\tt"DRUR"$。特别地,我们可以**任取**起始点,因为无论取哪个点,最终都能还原出整个零件,结果相同。
但我们可能遇到类似$\textbf{零件J}$的困难:
$$\begin{matrix}&\bigcirc \cr&|\cr\bigcirc-\kern{-12pt}&\bigcirc-\kern{-12pt}&\bigcirc \cr&|\cr&\bigcirc\end{matrix}$$
我们无法避免经过重复的格子。这使得我们需要进行去重操作。事实上,可以引入一个新的指令$\verb!'<'!$,表示**回到上一个位置**。那么,如果我们取左侧的点作为起始点,$\textbf{零件J}$就能够表示为$\verb!"RU<D<R"!$。不重复之前经过的点,就可以避免去重这个问题了。
通过这种方式处理十二个零件,就可以大大减少码量。我们设起始点坐标为$(0,0)$,根据上述描述的指令进行遍历,就能求出每个零件。选取**左上角**,计算出剩余部分的**相对坐标**。
接着我们还需要处理一个棘手的问题:零件可以**旋转**,**翻转**。
事实上,这个问题可以很容易地解决。假如,我们将**上看成右**,**右看成下**,**下看成左**,**左看成上**,重新进行构造,就相当于进行了$90\degree$旋转,同理可以旋转$180\degree,270\degree$;翻转只要将上下颠倒就行了,即将上看成下,下看成上。有些零件并不需要处理过多的旋转、翻转操作。我们可以用常量数组存储需要进行哪些操作。
处理完存储$12$个零件的问题,剩下来的事情就是暴力搜索了。我们从上到下,从左到右考虑每个格子。枚举这个格子选择哪个零件,并进行深搜。之所以上文要以左上角作为参考点,就是为了防止填充的零件影响到之前搜索的点。如果需要影响到前面的点,那么前面的点就需要考虑**不填充零件**这一种特殊情况,无疑大大增加了枚举的复杂度。
此外,使用指针等方式,还可以进一步缩小码量。最终,这一道码农题就成功被我们用$2\rm kB$左右的代码写完了。
## 参考代码
```cpp
#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;
}
```