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

囧仙

2020-05-26 23:49:58

Solution

## 题目大意 用$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; } ```