1501: [NOI2005]智慧珠游戏
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 190 Solved: 122
[Submit][Status]
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.........
..
...
....
.....
.....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=0; bool flag=false; do ch=(char)getchar(),flag=(ch=='-')?true:flag; while(ch<'0'||ch>'9'); do x=x*10+ch-'0'; while (ch=(char)getchar(),ch<='9' && ch>='0'); return x*(flag?-1:1); } int n,m; const int tots[MAXS]={3,4,4,4,5,5,5,5,5,5,5,5}; const int fs_s[MAXS][5][2]= {{{0,0},{0,1},{1,0},{inf,inf},{inf,inf}}, {{0,0},{0,1},{0,2},{0,3},{inf,inf}}, {{0,0},{0,1},{0,2},{1,0},{inf,inf}}, {{0,0},{0,1},{1,0},{1,1},{inf,inf}}, {{0,0},{0,1},{0,2},{1,0},{2,0}}, {{0,0},{0,1},{0,2},{0,3},{1,1}}, {{0,0},{1,0},{0,1},{0,2},{1,2}}, {{0,0},{0,1},{0,2},{1,0},{1,1}}, {{0,0},{0,1},{0,2},{1,2},{1,3}}, {{0,0},{0,1},{1,0},{0,-1},{-1,0}}, {{0,0},{1,0},{1,1},{2,1},{2,2}}, {{0,0},{0,1},{0,2},{0,3},{1,0}}}; int fs[8][MAXS][5][2]; char mm[11][11]; struct DLX_t { static const int maxn=124; static const int maxm=124; static const int maxd=2000000; 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()-1]; topt=0; // 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=0;i<vec.size();i++) { chd[vec[i]]=++topt; col[chd[vec[i]]]=vec[i]; id[chd[vec[i]]]=0; 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[11][11]; int i,j,k1,k2; int x,y,z,d; for (i=0;i<10;i++) { for (j=0;j<10;j++) { mp[i][j]='.'; } } bool flag=false; for (i=0;i<res.size();i++) { if (res[i]==-1) { flag=true; continue; } d=res[i]/1200; x=res[i]%1200/120; y=res[i]%120/12; z=res[i]%12; for (j=0;j<tots[z];j++) { mp[x+fs[d][z][j][0]][y+fs[d][z][j][1]]=z+'A'; } } for (i=0;i<10;i++) { for (j=0;j<=i;j++) { if (mm[i+1][j+1]!='.') printf("%c",mm[i+1][j+1]); else printf("%c",mp[i][j]); } printf(" "); } printf(" "); } void print2() { int i; for (i=0;i<res.size();i++) { printf("%d ",res[i]); } printf(" "); } void Add_row(int name,vector<int> &vec) { int i; int nowh; int now; // sort(vec.begin(),vec.end()); for (i=0;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[0]]]]=R[U[chd[vec[0]]]]=U[chd[vec[0]]]; nowh=U[chd[vec[0]]]; for (i=1;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=0;i<MAXS;i++) for (j=0;j<5;j++) for (k=0;k<2;k++) fs[0][i][j][k]=fs_s[i][j][k]; for (kk=1;kk<4;kk++) { for (i=0;i<MAXS;i++) { for (j=0;j<tots[i];j++) { fs[kk][i][j][0]=fs[kk-1][i][j][1]; fs[kk][i][j][1]=-fs[kk-1][i][j][0]; } } } for (kk=4;kk<8;kk++) { for (i=0;i<MAXS;i++) { for (j=0;j<tots[i];j++) { fs[kk][i][j][0]=-fs[kk-4][i][j][0]; fs[kk][i][j][1]=fs[kk-4][i][j][1]; } } } /* 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(" "); } printf(" "); } }*/ } bool used[12]; bool state[130]; 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=1;i<=10;i++) { for (j=1;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'+100]=true; state[(i-1)*10+j-1]=true; } } scanf(" "); } for (i=1;i<=10;i++) { for (j=i+1;j<=10;j++) { state[(i-1)*10+j-1]=true; } } vector<int>::iterator it1; for (i=0;i<112;i++) { if (!state[i])upos.push_back(i); } //for (i=0;i<upos.size();i++) // cout<<upos[i]<<" "; //cout<<endl; DLX.init(112,upos); bool flag,flag2; int nowid; for (i=0;i<12;i++) { if (used[i])continue; for (kk=0;kk<8;kk++) { flag2=false; for (k=0;k<kk;k++) { flag=true; for (j=0;j<tots[i];j++) { if (fs[kk][i][j][0]!=fs[k][i][j][0] ||fs[kk][i][j][1]!=fs[k][i][j][1]) { flag=false; break; } } if (flag) { flag2=true; break; } } if (flag2) continue; for (x=1;x<=10;x++) { for (y=1;y<=x;y++) { flag=true; for (j=0;j<tots[i];j++) { if (x+fs[kk][i][j][0]<1 || x+fs[kk][i][j][0]>10 || y+fs[kk][i][j][1]<1 || y+fs[kk][i][j][1]>10 || y+fs[kk][i][j][1]>x+fs[kk][i][j][0] || mm[x+fs[kk][i][j][0]][y+fs[kk][i][j][1]]!='.') { flag=false; break; } } if (!flag)continue; //[dir][posx][posy][shape] //1200 120 12 1 nowid=kk*1200+(x-1)*120+(y-1)*12+i; tvec.clear(); tvec.push_back(100+i); for (j=0;j<tots[i];j++) { //[pos][shape(+1)] //100 +12 tvec.push_back((x+fs[kk][i][j][0]-1)*10+y+fs[kk][i][j][1]-1); } DLX.Add_row(nowid,tvec); } } } } if (!DLX.dfs()) printf("No solution "); return 0; }