题解 P4205 【[NOI2005]智慧珠游戏 】
先%%%一波巨佬U62267 BJpers2 这题是我们一道考试题，考试时候没做出来，以下是巨佬教本蒟蒻的做法，只有180行不到，不需太高码力就可敲出一道货真价实的黑题，黑题啊！！！（人生中第一道黑题）
巨佬的洛谷号https://www.luogu.org/space/show?uid=62267
题目大家应该都能看懂，就是搜索。
首先比较麻烦的就是各种零件可以翻转，旋转，这里我们可以考虑先打表表示出原来的图形，再用函数算出各种变换，注意有些图形可以转不转都一样，要特判处理搜索时节约时间，最后用图的形式存起来完成预处理。
然后就是搜索，讲一下剪枝的小技巧：玩过这种游戏的人大概都体会到那些形状奇奇怪怪的零件最难放进去，所以我们可以规定一个搜索顺序，将难的先搜了剪枝越早越节约时间嘛。然后并查集判联通块，我们发现没有小于3的零件，因此联通块小于3剪掉，没有两个联通块可以拼成6的大小，所以6也剪掉；
最后第8个点还是T了。。因为无解的情况需要全搜一遍最慢。。于是毫无意外地爆炸了。。然后另一位巨佬U109236 Fuyuki提出了WCX剪枝，开一个时间变量，如果时间大于950ms直接输出“No solution”；终于AC;
另一位巨佬的洛谷号https://www.luogu.org/space/show?uid=109236
以下放代码：
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstring>
#include<cstdlib>
#define FOR(i,a,b) for(register int i=a;i<=b;i++)
#define ROF(i,a,b) for(register int i=a;i>=b;i--)
#define TU(x) for(register int k=head[x],v=e[k].to;k;k=e[k].from,v=e[k].to)
using namespace std;
const int N=100,S=5,M=400;
clock_t start,end;
struct Edge
{
int from,to;
}e[M];//前向星存图
char a[N][S][S]=//打表大法好
{
{"AA",
"A."//0
},{"BBBB"},//1
{"CCC",
"C.."//2
},
{"DD",
"DD"//3
},
{"E..",
"E..",
"EEE"//4
},
{"FFFF",
".F.."//5
},
{"GGG",
"G.G"//6
},
{"HHH",
"HH." //7
},
{"III.",
"..II"//8
},
{".J.",
"JJJ",//9
".J."
},
{"K..",
"KK.",//10
".KK"
},
{"LLLL",
"L..."//11
}
},Map[15][15];
int vis[N],cnt,head[N],f[N],sz[N],cc=12;
int dx[4]={-1,+0,+1,+0},dy[4]={+0,+1,+0,-1};
int r[N]={2,1,2,2,3,2,2,2,2,3,3,2};//每个零件的宽度
int c[N]={2,4,3,2,3,4,3,3,4,3,3,4};//每个零件的长度
int df[12]={9,8,10,6,5,11,7,4,2,0,1,3};//规定搜索顺序，先把难填的填进去，方便剪枝
void add(int x,int y)//存边
{
e[++cnt].from=head[x];
e[cnt].to=y;
head[x]=cnt;
}
void zhuan(char p[S][S],int x,int y,char q[S][S]){
FOR(i,0,x-1)FOR(j,0,y-1)q[y-j-1][i]=p[i][j];}
//旋转
void fan(char p[S][S],int x,int y,char q[S][S]){
FOR(i,0,x-1)FOR(j,0,y-1)q[i][y-j-1]=p[i][j];}
//对称
inline int g(int x,int y){return (x-1)*10+y;}//二维变一维
int getf(int q){return f[q]==q?q:f[q]=getf(f[q]);}//并查集
void Merge(int x,int y)
{
int fa=getf(x),fb=getf(y);
if(fa!=fb)f[fa]=fb,sz[fb]+=sz[fa];//sz数组存联通块大小
}//合并
void dfs(int num)
{
if(num>=9)
{
end=clock();//WeiChenxuan剪枝
if(double(end-start)/double(CLOCKS_PER_SEC)>=0.9)
{
cout<<"No solution"<<endl;
exit(0);
}
}
int x=df[num];
if(vis[x])
{
dfs(num+1);
return;
}
if(num>11)
{
FOR(i,1,10)
{
FOR(j,1,i)cout<<Map[i][j];//找到结果，输出
cout<<endl;
}
exit(0);
}
FOR(i,1,10)FOR(j,1,i){f[g(i,j)]=g(i,j);sz[g(i,j)]=1;}//并查集初始化
FOR(i,1,10)FOR(j,1,i)
if(Map[i][j]=='.')FOR(k,0,3)
{
int nx=i+dx[k],ny=j+dy[k];//判联通块
if(Map[nx][ny]=='.')Merge(g(i,j),g(nx,ny));
}
FOR(i,1,10)FOR(j,1,i)if(Map[i][j]=='.')
{
int ss=sz[getf(g(i,j))];//利用联通块大小剪枝
if(ss<3 || ss==6)return;
}
TU(x)
{
FOR(i,1,10)FOR(j,1,i)
{
bool ok=1;
FOR(p,0,r[v]-1)
{
FOR(q,0,c[v]-1)
if(a[v][p][q]>='A' && a[v][p][q]<='L' && Map[i+p][j+q]!='.')
{ok=0;break;}//判断能否放入
if(!ok)break;
}
if(ok)
{
FOR(p,0,r[v]-1)FOR(q,0,c[v]-1)
if(a[v][p][q]!='.')Map[i+p][j+q]=a[v][p][q];
dfs(num+1);
FOR(p,0,r[v]-1)FOR(q,0,c[v]-1)
if(a[v][p][q]!='.')Map[i+p][j+q]='.';
}
}
}
}
int main()
{
FOR(i,0,11)
{
zhuan(a[i],r[i],c[i],a[++cc]);//左转90°
r[cc]=c[i];c[cc]=r[i];
zhuan(a[cc],r[cc],c[cc],a[cc+1]);//左转180°
r[++cc]=r[i];c[cc]=c[i];
zhuan(a[cc],r[cc],c[cc],a[cc+1]);//左转270°=右转90°
r[++cc]=c[i];c[cc]=r[i];
add(i,i);
if(i==3 || i==9)continue;
add(i,cc-2);
if(i==1)continue;
add(i,cc-1);add(i,cc);
if(i==0 || i==4 || i==10 || i==6)continue;
int t0=i,t1=cc,t2=cc-2,t3=cc-1;
fan(a[t0],r[t0],c[t0],a[++cc]);//原图对称
r[cc]=r[t0];c[cc]=c[t0];
fan(a[t1],r[t1],c[t1],a[++cc]);//左转后对称
r[cc]=r[t1];c[cc]=c[t1];
fan(a[t2],r[t2],c[t2],a[++cc]);//180后对称
r[cc]=r[t2];c[cc]=c[t2];
fan(a[t3],r[t3],c[t3],a[++cc]);//右转后对称
r[cc]=r[t3];c[cc]=c[t3];
add(i,cc);add(i,cc-1);add(i,cc-2);add(i,cc-3);
}char ch;
FOR(i,1,15)FOR(j,1,15)Map[i][j]='#';
FOR(i,1,10)
FOR(j,1,i)
{
ch=getchar();while(ch!='.' && (ch<'A' || ch>'L'))ch=getchar();//强行快读
Map[i][j]=ch;
if(ch!='.')vis[ch-'A']=1;
}
start=clock();
dfs(0);
cout<<"No solution"<<endl;
return 0;
}