1501: [NOI2005]智慧珠游戏
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 190 Solved: 122
[Submit][Status]
Description
![bzoj 1501: [NOI2005]智慧珠游戏 Dancing Link](https://image.shishitao.com:8440/aHR0cDovL3d3dy5seWRzeS5jb20vSnVkZ2VPbmxpbmUvaW1hZ2VzLzE1MDFfMS5qcGc%3D.jpg?w=700&webp=1 "bzoj 1501: [NOI2005]智慧珠游戏 Dancing Link")
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.........
..
...
....
.....
.....C
...CCC.
EEEHH...
E.HHH....
E.........
Sample Output
B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF
HINT
Source
多虧八中時限開的比較寬，我那個其醜無比的DLX才恰好過去了，不知道其他大神是怎麼優化成0ms的。
作爲DLX的模板，還是貼一下。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<queue>
using namespace std;
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#define MAXN 1100
#define MAXV MAXN*2
#define MAXE MAXV*2
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define inf INF
#define MAXS 12
typedef long long qword;
inline int nextInt()
{
char ch;
int x=;
bool flag=false;
do
ch=(char)getchar(),flag=(ch=='-')?true:flag;
while(ch<''||ch>'');
do x=x*+ch-'';
while (ch=(char)getchar(),ch<='' && ch>='');
return x*(flag?-:);
}
int n,m;
const int tots[MAXS]={,,,,,,,,,,,};
const int fs_s[MAXS][][]=
{{{,},{,},{,},{inf,inf},{inf,inf}},
{{,},{,},{,},{,},{inf,inf}},
{{,},{,},{,},{,},{inf,inf}},
{{,},{,},{,},{,},{inf,inf}},
{{,},{,},{,},{,},{,}},
{{,},{,},{,},{,},{,}},
{{,},{,},{,},{,},{,}},
{{,},{,},{,},{,},{,}},
{{,},{,},{,},{,},{,}},
{{,},{,},{,},{,-},{-,}},
{{,},{,},{,},{,},{,}},
{{,},{,},{,},{,},{,}}};
int fs[][MAXS][][];
char mm[][];
struct DLX_t
{
static const int maxn=;
static const int maxm=;
static const int maxd=;
int m;
int head;
int L[maxd],R[maxd],U[maxd],D[maxd];
int id[maxd];
int topt;
int chd[maxm];
int col[maxd];
int tt[maxm];
vector<int> res;
void init(int mm,vector<int> &vec)
{
m=vec[vec.size()-];
topt=;
// memset(L,0,sizeof(L));
// memset(R,0,sizeof(R));
// memset(D,0,sizeof(D));
// memset(U,0,sizeof(U));
// memset(tt,0,sizeof(tt));
res.clear();
head=++topt;
L[head]=R[head]=head;
U[head]=D[head]=head;
int i;
for (i=;i<vec.size();i++)
{
chd[vec[i]]=++topt;
col[chd[vec[i]]]=vec[i];
id[chd[vec[i]]]=;
R[chd[vec[i]]]=head;
L[chd[vec[i]]]=L[head];
R[L[chd[vec[i]]]]=chd[vec[i]];
L[R[chd[vec[i]]]]=chd[vec[i]];
U[chd[vec[i]]]=D[chd[vec[i]]]=chd[vec[i]];
}
}
void print()
{
char mp[][];
int i,j,k1,k2;
int x,y,z,d;
for (i=;i<;i++)
{
for (j=;j<;j++)
{
mp[i][j]='.';
}
}
bool flag=false;
for (i=;i<res.size();i++)
{
if (res[i]==-)
{
flag=true;
continue;
}
d=res[i]/;
x=res[i]%/;
y=res[i]%/;
z=res[i]%;
for (j=;j<tots[z];j++)
{
mp[x+fs[d][z][j][]][y+fs[d][z][j][]]=z+'A';
}
}
for (i=;i<;i++)
{
for (j=;j<=i;j++)
{
if (mm[i+][j+]!='.')
printf("%c",mm[i+][j+]);
else
printf("%c",mp[i][j]);
}
printf("\n");
}
printf("\n"); }
void print2()
{
int i;
for (i=;i<res.size();i++)
{
printf("%d ",res[i]);
}
printf("\n"); }
void Add_row(int name,vector<int> &vec)
{
int i;
int nowh;
int now;
// sort(vec.begin(),vec.end());
for (i=;i<vec.size();i++)
{
now=++topt;
id[now]=name;
col[now]=vec[i];
tt[vec[i]]++;
U[now]=U[chd[vec[i]]];
D[now]=chd[vec[i]];
D[U[now]]=now;
U[D[now]]=now;
}
L[U[chd[vec[]]]]=R[U[chd[vec[]]]]=U[chd[vec[]]];
nowh=U[chd[vec[]]];
for (i=;i<vec.size();i++)
{
now=U[chd[vec[i]]];
R[now]=nowh;
L[now]=L[nowh];
R[L[now]]=now;
L[R[now]]=now; }
}
void finish()
{
print();
}
void cover(int c)
{
R[L[chd[c]]]=R[chd[c]];
L[R[chd[c]]]=L[chd[c]];
int i,j;
for (i=D[chd[c]];i!=chd[c];i=D[i])
{
for (j=R[i];j!=i;j=R[j])
{
tt[col[j]]--;
U[D[j]]=U[j];
D[U[j]]=D[j];
}
}
}
void resume(int c)
{
int i,j;
R[L[chd[c]]]=chd[c];
L[R[chd[c]]]=chd[c];
for (i=D[chd[c]];i!=chd[c];i=D[i])
{
for (j=R[i];j!=i;j=R[j])
{
tt[col[j]]++;
U[D[j]]=j;
D[U[j]]=j;
}
} }
bool dfs()
{
if (head==L[head])
{
finish();
return true;
}
int i,j;
int bc,bst=INF;
for (i=R[head];i!=head;i=R[i])
{
if (D[i]==i)return false;
if (tt[col[i]]<bst)
{
bst=tt[col[i]];
bc=col[i];
}
}
cover(bc);
for (i=D[chd[bc]]; i!=chd[bc] ;i=D[i])
{
res.push_back(id[i]);
for (j=R[i];j!=i;j=R[j])
cover(col[j]);
if (dfs())return true;
res.pop_back();
for (j=R[i];j!=i;j=R[j])
resume(col[j]);
}
resume(bc);
return false;
}
}DLX;
void init()
{
int i,j,k,kk;
for (i=;i<MAXS;i++)
for (j=;j<;j++)
for (k=;k<;k++)
fs[][i][j][k]=fs_s[i][j][k];
for (kk=;kk<;kk++)
{
for (i=;i<MAXS;i++)
{
for (j=;j<tots[i];j++)
{
fs[kk][i][j][]=fs[kk-][i][j][];
fs[kk][i][j][]=-fs[kk-][i][j][];
}
}
}
for (kk=;kk<;kk++)
{
for (i=;i<MAXS;i++)
{
for (j=;j<tots[i];j++)
{
fs[kk][i][j][]=-fs[kk-][i][j][];
fs[kk][i][j][]=fs[kk-][i][j][];
}
}
}
/* char mp[8][8];
for (i=0;i<MAXS;i++)
{
for (kk=0;kk<1;kk++)
{
memset(mp,0,sizeof(mp));
for (j=0;j<tots[i];j++)
{
mp[fs[kk][i][j][0]+4][fs[kk][i][j][1]+4]=true;
}
for (j=0;j<8;j++)
{
for (k=0;k<8;k++)
{
printf("%c",mp[j][k]?'.':'#');
}
printf("\n");
}
printf("\n"); }
}*/
}
bool used[];
bool state[];
vector<int> upos,tvec,pcol;
int main()
{
freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int i,j,k,kk;
int x,y,z;
/*
DLX.init(5);
tvec.clear();
tvec.push_back(0);
tvec.push_back(2);
tvec.push_back(3);
DLX.Add_row(1,tvec);
tvec.clear();
tvec.push_back(2);
tvec.push_back(3);
tvec.push_back(4);
DLX.Add_row(1,tvec);
tvec.clear();
tvec.push_back(1);
tvec.push_back(3);
DLX.Add_row(1,tvec);
tvec.clear();
tvec.push_back(1);
tvec.push_back(4);
DLX.Add_row(1,tvec);
cout<<DLX.dfs()<<endl;
return 0;*/
init();
char ch;
for (i=;i<=;i++)
{
for (j=;j<=i;j++)
{
scanf("%c",&ch);
// pcol.push_back((i-1)*10+j-1);
mm[i][j]=ch;
if (ch!='.')
{
used[ch-'A']=true;
state[ch-'A'+]=true;
state[(i-)*+j-]=true;
}
}
scanf("\n");
}
for (i=;i<=;i++)
{
for (j=i+;j<=;j++)
{
state[(i-)*+j-]=true;
}
}
vector<int>::iterator it1;
for (i=;i<;i++)
{
if (!state[i])upos.push_back(i);
}
//for (i=0;i<upos.size();i++)
// cout<<upos[i]<<" ";
//cout<<endl;
DLX.init(,upos);
bool flag,flag2;
int nowid;
for (i=;i<;i++)
{
if (used[i])continue;
for (kk=;kk<;kk++)
{
flag2=false;
for (k=;k<kk;k++)
{
flag=true;
for (j=;j<tots[i];j++)
{
if (fs[kk][i][j][]!=fs[k][i][j][]
||fs[kk][i][j][]!=fs[k][i][j][])
{
flag=false;
break;
}
}
if (flag)
{
flag2=true;
break;
}
}
if (flag2)
continue;
for (x=;x<=;x++)
{
for (y=;y<=x;y++)
{
flag=true;
for (j=;j<tots[i];j++)
{
if (x+fs[kk][i][j][]< || x+fs[kk][i][j][]>
|| y+fs[kk][i][j][]< || y+fs[kk][i][j][]>
|| y+fs[kk][i][j][]>x+fs[kk][i][j][]
|| mm[x+fs[kk][i][j][]][y+fs[kk][i][j][]]!='.')
{
flag=false;
break;
}
}
if (!flag)continue;
//[dir][posx][posy][shape]
//1200 120 12 1
nowid=kk*+(x-)*+(y-)*+i;
tvec.clear();
tvec.push_back(+i);
for (j=;j<tots[i];j++)
{
//[pos][shape(+1)]
//100 +12
tvec.push_back((x+fs[kk][i][j][]-)*+y+fs[kk][i][j][]-);
}
DLX.Add_row(nowid,tvec);
}
}
}
}
if (!DLX.dfs())
printf("No solution\n");
return ;
}