[BZOJ]1501智慧珠游戏[NOI2005]
Description
Input
文件中包含初始的盘件描述，一共有10行，第i行有i个字符。如果第i行的第j个字符是字母”A”至”L”中的一个，则表示第i行第j列的格子上已经放了零件，零件的编号为对应的字母。如果第i行的第j个字符是”.”，则表示第i行第j列的格子上没有放零件。输入保证预放的零件已摆放在盘件中。
Output
如果能找到解，向输出文件打印10行，为放完全部12个零件后的布局。其中，第i行应包含i个字符，第i行的第j个字符表示第i行第j列的格子上放的是哪个零件。如果无解，输出单独的一个字符串‘No solution’(不要引号，请注意大小写)。所有的数据保证最多只有一组解。
Sample Input
.
..
...
....
.....
.....C
...CCC.
EEEHH...
E.HHH....
E.........
Sample Output
B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF
思路
DLX
每个table[i][j]表示第i个图形的第j个格子与第0个格子的横纵坐标差值（不是加绝对值的那种差值），
然后用的时候进行枚举
Ⅰ.每个点的｛a,b｝中a应该加到x还是y上，
Ⅱ.每个点的x值需要加还是减，
Ⅲ.每个点的y值需要加还是减。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=30000;
const int M=55+12+10;
#define inf 0x3f
const int lenx[20]={3,4,4,4,5,5,5,5,5,5,5,5};
const int table[15][10][5]=
{
{{0,0},{1,0},{0,1}},
{{0,0},{0,1},{0,2},{0,3}},
{{0,0},{1,0},{0,1},{0,2}},
{{0,0},{1,0},{0,1},{1,1}},
{{0,0},{1,0},{2,0},{2,1},{2,2}},
{{0,0},{0,1},{1,1},{0,2},{0,3}},
{{0,0},{1,0},{0,1},{0,2},{1,2}},
{{0,0},{1,0},{0,1},{1,1},{0,2}},
{{0,0},{0,1},{0,2},{1,2},{1,3}},
{{0,0},{-1,1},{0,1},{1,1},{0,2}},
{{0,0},{1,0},{1,1},{2,1},{2,2}},
{{0,0},{1,0},{0,1},{0,2},{0,3}}
};
const int crsx[60]=
{
0 ,
1 ,
2 ,2 ,
3 ,3 ,3 ,
4 ,4 ,4 ,4 ,
5 ,5 ,5 ,5 ,5 ,
6 ,6 ,6 ,6 ,6 ,6 ,
7 ,7 ,7 ,7 ,7 ,7 ,7 ,
8 ,8 ,8 ,8 ,8 ,8 ,8 ,8 ,
9 ,9 ,9 ,9 ,9 ,9 ,9 ,9 ,9 ,
10,10,10,10,10,10,10,10,10,10
};
const int crsy[60]=
{
0 ,
1 ,
1 ,2 ,
1 ,2 ,3 ,
1 ,2 ,3 ,4 ,
1 ,2 ,3 ,4 ,5 ,
1 ,2 ,3 ,4 ,5 ,6 ,
1 ,2 ,3 ,4 ,5 ,6 ,7 ,
1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,
1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,
1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10,
};
char TS[30][30];
#define NN 16000
struct DLX
{
int elist,eline;
int stid[30][30];
int eid[M];
int fid[NN];
bool visit[30];
int U[NN],D[NN],L[NN],R[NN],C[NN],V[NN];
int H[NN],T[M],cnt;
int ans[30][30];
inline void newnode(int x,int y)
{
C[++cnt]=y;V[cnt]=x;T[y]++;
if(!H[x])H[x]=L[cnt]=R[cnt]=cnt;
else L[cnt]=H[x],R[cnt]=R[H[x]];
R[H[x]]=L[R[H[x]]]=cnt,H[x]=cnt;
U[cnt]=U[y],D[cnt]=y;
U[y]=D[U[y]]=cnt;
}
inline void remove(int x)
{
for(int i=D[x];i!=x;i=D[i])
for(int j=R[i];j!=i;j=R[j])
{
U[D[j]]=U[j];
D[U[j]]=D[j];
T[C[j]]--;
}
L[R[x]]=L[x];
R[L[x]]=R[x];
}
inline void resume(int x)
{
for(int i=U[x];i!=x;i=U[i])
for(int j=L[i];j!=i;j=L[j])
{
U[D[j]]=j;
D[U[j]]=j;
T[C[j]]++;
}
L[R[x]]=x;
R[L[x]]=x;
}
inline void build()
{
int ti[2],i,j,k;
for(i=1;i<=10;i++)for(j=1;j<=i;j++)if(TS[i][j]!='.')visit[TS[i][j]-'A']=1;
for(i=1;i<=10;i++)for(j=1;j<=i;j++)stid[i][j]=++elist;
cnt=elist+12;
for(i=1;i<=cnt;i++)
{
U[i]=D[i]=i;
L[i]=L[0],R[i]=0;
L[0]=R[L[0]]=i;
}
int tx,xm,ym,shape;
int nx[2],mul[2]={-1,1};
for(shape=0;shape<12;shape++)
{
elist++;
for(tx=0;tx<2;tx++)
for(xm=0;xm<2;xm++)
for(ym=0;ym<2;ym++)
for(ti[0]=1;ti[0]<=10;ti[0]++)
for(ti[1]=1;ti[1]<=ti[0];ti[1]++)
{
for(k=0;k<lenx[shape];k++)
{
nx[ tx ]=ti[ tx ]+mul[xm]*table[shape][k][0];
nx[tx^1]=ti[tx^1]+mul[ym]*table[shape][k][1];
if(visit[shape]){if(TS[nx[0]][nx[1]]!='A'+shape)break;}
else if(TS[nx[0]][nx[1]]!='.')break;
}
if(k==lenx[shape])
{
fid[++eline]=shape;
for(k=0;k<lenx[shape];k++)
{
nx[ tx ]=ti[ tx ]+mul[xm]*table[shape][k][0];
nx[tx^1]=ti[tx^1]+mul[ym]*table[shape][k][1];
newnode(eline,stid[nx[0]][nx[1]]);
}
newnode(eline,elist);
}
}
}
}
inline bool dfs()
{
if(!R[0])return true;
int S=R[0],W=T[S],i,j;
for(i=R[S];i;i=R[i])
if(T[i]<W)
{
W=T[i];
S=i;
}
remove(S);
for(i=D[S];i!=S;i=D[i])
{
if(C[i]<=55)ans[crsx[C[i]]][crsy[C[i]]]=fid[V[i]];
for(j=R[i];j!=i;j=R[j])
{
remove(C[j]);
if(C[j]<=55)
ans[crsx[C[j]]][crsy[C[j]]]=fid[V[j]];
}
if(dfs()) return true;
for(j=L[i];j!=i;j=L[j]) resume(C[j]);
}
resume(S);
return false;
}
inline void ret()
{
for(int i=1;i<=10;i++)
{
for(int j=1;j<=i;j++)printf("%c",ans[i][j]+'A');
puts("");
}
}
inline void work()
{
build();
if(dfs())ret();
else puts("No solution");
}
}dlx;
int main()
{
for(int i=1;i<=10;i++) scanf("%s",TS[i]+1);
dlx.work();
return 0;
}