首页 > 代码库 > BZOJ1501 (NOI2005 智慧珠游戏）
BZOJ1501 (NOI2005 智慧珠游戏）
传送门@百度
1501: [NOI2005]智慧珠游戏
Time Limit: 5 Sec Memory Limit: 64 MBDescription
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
Dance Link
恩一道非常恶心的搜索题，不过没学dancing Links所以这题的剪枝是抄别人开头的可行性剪枝。。
#include<set>#include<map>#include<cmath>#include<queue>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>using namespace std;const int N = 150;#define rep(i,n) for(int i=0;i<n;i++)#define Rep(i,n) for(int i=1;i<=n;i++)#define For(i,l,r) for(int i=l;i<=r;i++)struct Ret{ int tot,cnt,x[8][5],y[8][5]; Ret():tot(0),cnt(0){memset(x,0,sizeof(x)),memset(y,0,sizeof(y));} Ret(int p){ switch(p){ case ‘A‘: cnt=4,tot=2; x[0][0]=1,y[0][0]=0; x[0][1]=0,y[0][1]=1; x[1][0]=1,y[1][0]=0; x[1][1]=1,y[1][1]=1; x[2][0]=0,y[2][0]=1; x[2][1]=1,y[2][1]=1; x[3][0]=1,y[3][0]=0; x[3][1]=1,y[3][1]=-1; break; case ‘B‘: cnt=2,tot=3; x[0][0]=0,y[0][0]=1; x[0][1]=0,y[0][1]=2; x[0][2]=0,y[0][2]=3; x[1][0]=1,y[1][0]=0; x[1][1]=2,y[1][1]=0; x[1][2]=3,y[1][2]=0; break; case ‘C‘: cnt=8,tot=3; x[0][0]=0,y[0][0]=1; x[0][1]=0,y[0][1]=2; x[0][2]=1,y[0][2]=0; x[1][0]=0,y[1][0]=1; x[1][1]=1,y[1][1]=1; x[1][2]=2,y[1][2]=1; x[2][0]=1,y[2][0]=-2; x[2][1]=1,y[2][1]=-1; x[2][2]=1,y[2][2]=0; x[3][0]=1,y[3][0]=0; x[3][1]=2,y[3][1]=0; x[3][2]=2,y[3][2]=1; x[4][0]=1,y[4][0]=0; x[4][1]=2,y[4][1]=0; x[4][2]=2,y[4][2]=-1; x[5][0]=1,y[5][0]=0; x[5][1]=1,y[5][1]=1; x[5][2]=1,y[5][2]=2; x[6][0]=0,y[6][0]=1; x[6][1]=1,y[6][1]=0; x[6][2]=2,y[6][2]=0; x[7][0]=0,y[7][0]=1; x[7][1]=0,y[7][1]=2; x[7][2]=1,y[7][2]=2; break; case ‘D‘: cnt=1,tot=3; x[0][0]=0,y[0][0]=1; x[0][1]=1,y[0][1]=0; x[0][2]=1,y[0][2]=1; break; case ‘E‘: cnt=4,tot=4; x[0][0]=0,y[0][0]=1; x[0][1]=0,y[0][1]=2; x[0][2]=1,y[0][2]=0; x[0][3]=2,y[0][3]=0; x[1][0]=1,y[1][0]=0; x[1][1]=2,y[1][1]=0; x[1][2]=2,y[1][2]=1; x[1][3]=2,y[1][3]=2; x[2][0]=0,y[2][0]=1; x[2][1]=0,y[2][1]=2; x[2][2]=1,y[2][2]=2; x[2][3]=2,y[2][3]=2; x[3][0]=2,y[3][0]=-2; x[3][1]=2,y[3][1]=-1; x[3][2]=2,y[3][2]=0; x[3][3]=1,y[3][3]=0; break; case ‘F‘: cnt=8,tot=4; x[0][0]=0,y[0][0]=1; x[0][1]=1,y[0][1]=1; x[0][2]=0,y[0][2]=2; x[0][3]=0,y[0][3]=3; x[1][0]=1,y[1][0]=0; x[1][1]=2,y[1][1]=0; x[1][2]=3,y[1][2]=0; x[1][3]=2,y[1][3]=1; x[2][0]=1,y[2][0]=-2; x[2][1]=1,y[2][1]=-1; x[2][2]=1,y[2][2]=0; x[2][3]=1,y[2][3]=1; x[3][0]=1,y[3][0]=-1; x[3][1]=1,y[3][1]=0; x[3][2]=2,y[3][2]=0; x[3][3]=3,y[3][3]=0; x[4][0]=1,y[4][0]=0; x[4][1]=1,y[4][1]=1; x[4][2]=2,y[4][2]=0; x[4][3]=3,y[4][3]=0; x[5][0]=1,y[5][0]=-1; x[5][1]=1,y[5][1]=0; x[5][2]=1,y[5][2]=1; x[5][3]=1,y[5][3]=2; x[6][0]=1,y[6][0]=0; x[6][1]=2,y[6][1]=0; x[6][2]=1,y[6][2]=-1; x[6][3]=3,y[6][3]=0; x[7][0]=0,y[7][0]=1; x[7][1]=0,y[7][1]=2; x[7][2]=1,y[7][2]=2; x[7][3]=0,y[7][3]=3; break; case ‘G‘: cnt=4,tot=4; x[0][0]=1,y[0][0]=0; x[0][1]=0,y[0][1]=1; x[0][2]=0,y[0][2]=2; x[0][3]=1,y[0][3]=2; x[1][0]=0,y[1][0]=1; x[1][1]=1,y[1][1]=0; x[1][2]=2,y[1][2]=0; x[1][3]=2,y[1][3]=1; x[2][0]=1,y[2][0]=0; x[2][1]=1,y[2][1]=1; x[2][2]=1,y[2][2]=2; x[2][3]=0,y[2][3]=2; x[3][0]=0,y[3][0]=1; x[3][1]=1,y[3][1]=1; x[3][2]=2,y[3][2]=1; x[3][3]=2,y[3][3]=0; break; case ‘H‘: cnt=8,tot=4; x[0][0]=0,y[0][0]=1; x[0][1]=1,y[0][1]=0; x[0][2]=1,y[0][2]=1; x[0][3]=0,y[0][3]=2; x[1][0]=1,y[1][0]=1; x[1][1]=1,y[1][1]=0; x[1][2]=2,y[1][2]=1; x[1][3]=2,y[1][3]=0; x[2][0]=0,y[2][0]=1; x[2][1]=1,y[2][1]=0; x[2][2]=1,y[2][2]=1; x[2][3]=1,y[2][3]=-1; x[3][0]=0,y[3][0]=1; x[3][1]=1,y[3][1]=0; x[3][2]=1,y[3][2]=1; x[3][3]=2,y[3][3]=1; x[4][0]=0,y[4][0]=1; x[4][1]=1,y[4][1]=0; x[4][2]=1,y[4][2]=1; x[4][3]=2,y[4][3]=0; x[5][0]=0,y[5][0]=1; x[5][1]=1,y[5][1]=0; x[5][2]=1,y[5][2]=1; x[5][3]=1,y[5][3]=2; x[6][0]=1,y[6][0]=-1; x[6][1]=1,y[6][1]=0; x[6][2]=2,y[6][2]=-1; x[6][3]=2,y[6][3]=0; x[7][0]=0,y[7][0]=1; x[7][1]=0,y[7][1]=2; x[7][2]=1,y[7][2]=1; x[7][3]=1,y[7][3]=2; break; case ‘I‘: cnt=8,tot=4; x[0][0]=0,y[0][0]=1; x[0][1]=0,y[0][1]=2; x[0][2]=1,y[0][2]=2; x[0][3]=1,y[0][3]=3; x[1][0]=1,y[1][0]=-1; x[1][1]=1,y[1][1]=0; x[1][2]=2,y[1][2]=-1; x[1][3]=3,y[1][3]=-1; x[2][0]=0,y[2][0]=1; x[2][1]=1,y[2][1]=1; x[2][2]=1,y[2][2]=2; x[2][3]=1,y[2][3]=3; x[3][0]=1,y[3][0]=0; x[3][1]=2,y[3][1]=0; x[3][2]=2,y[3][2]=-1; x[3][3]=3,y[3][3]=-1; x[4][0]=1,y[4][0]=0; x[4][1]=2,y[4][1]=0; x[4][2]=2,y[4][2]=1; x[4][3]=3,y[4][3]=1; x[5][0]=1,y[5][0]=-2; x[5][1]=1,y[5][1]=-1; x[5][2]=1,y[5][2]=0; x[5][3]=0,y[5][3]=1; x[6][0]=1,y[6][0]=0; x[6][1]=1,y[6][1]=1; x[6][2]=2,y[6][2]=1; x[6][3]=3,y[6][3]=1; x[7][0]=1,y[7][0]=0; x[7][1]=1,y[7][1]=-1; x[7][2]=0,y[7][2]=1; x[7][3]=0,y[7][3]=2; break; case ‘J‘: cnt=1,tot=4; x[0][0]=1,y[0][0]=-1; x[0][1]=1,y[0][1]=0; x[0][2]=1,y[0][2]=1; x[0][3]=2,y[0][3]=0; break; case ‘K‘: cnt=4,tot=4; x[0][0]=1,y[0][0]=0; x[0][1]=1,y[0][1]=1; x[0][2]=2,y[0][2]=1; x[0][3]=2,y[0][3]=2; x[1][0]=1,y[1][0]=0; x[1][1]=1,y[1][1]=-1; x[1][2]=2,y[1][2]=-1; x[1][3]=2,y[1][3]=-2; x[2][0]=0,y[2][0]=1; x[2][1]=1,y[2][1]=1; x[2][2]=1,y[2][2]=2; x[2][3]=2,y[2][3]=2; x[3][0]=0,y[3][0]=1; x[3][1]=1,y[3][1]=0; x[3][2]=1,y[3][2]=-1; x[3][3]=2,y[3][3]=-1; break; case ‘L‘: cnt=8,tot=4; x[0][0]=0,y[0][0]=1; x[0][1]=0,y[0][1]=2; x[0][2]=0,y[0][2]=3; x[0][3]=1,y[0][3]=0; x[1][0]=0,y[1][0]=1; x[1][1]=1,y[1][1]=1; x[1][2]=2,y[1][2]=1; x[1][3]=3,y[1][3]=1; x[2][0]=1,y[2][0]=0; x[2][1]=1,y[2][1]=-1; x[2][2]=1,y[2][2]=-2; x[2][3]=1,y[2][3]=-3; x[3][0]=1,y[3][0]=0; x[3][1]=2,y[3][1]=0; x[3][2]=3,y[3][2]=0; x[3][3]=3,y[3][3]=1; x[4][0]=1,y[4][0]=0; x[4][1]=2,y[4][1]=0; x[4][2]=3,y[4][2]=0; x[4][3]=3,y[4][3]=-1; x[5][0]=1,y[5][0]=0; x[5][1]=1,y[5][1]=1; x[5][2]=1,y[5][2]=2; x[5][3]=1,y[5][3]=3; x[6][0]=1,y[6][0]=0; x[6][1]=2,y[6][1]=0; x[6][2]=3,y[6][2]=0; x[6][3]=0,y[6][3]=1; x[7][0]=0,y[7][0]=1; x[7][1]=0,y[7][1]=2; x[7][2]=0,y[7][2]=3; x[7][3]=1,y[7][3]=3; break; } }}opt[N];char a[10][10];bool used[N];bool Null(int x,int y,Ret &op,int l){ rep(i,op.tot) if(x+op.x[l][i]<1||y+op.y[l][i]<1||a[x+op.x[l][i]][y+op.y[l][i]]!=‘.‘) return false; return true;}void put(int x,int y,Ret &op,int l,char c){ rep(i,op.tot) a[x+op.x[l][i]][y+op.y[l][i]]=c;}bool DFS(int i,int j){ if(i<j) return DFS(i+1,1); if(i>10){ Rep(k,10) puts(a[k]+1); return true; } if(a[i][j]!=‘.‘) return DFS(i,j+1); for(int k=‘A‘;k<=‘L‘;k++) if(!used[k]){ used[k]=true;a[i][j]=k; rep(l,opt[k].cnt) if(Null(i,j,opt[k],l)){ put(i,j,opt[k],l,k); if(DFS(i,j+1)) return true; put(i,j,opt[k],l,‘.‘); } used[k]=false;a[i][j]=‘.‘; } return false;}bool valid(){ Rep(i,10) Rep(j,i) if(a[i][j]==‘.‘&&a[i][j+1]==‘.‘&&a[i][j-1]!=‘.‘&&a[i][j+2]!=‘.‘&&a[i-1][j]!=‘.‘&&a[i-1][j+1]!=‘.‘&&a[i+1][j]!=‘.‘&&a[i+1][j+1]!=‘.‘ ||a[i][j]==‘.‘&&a[i+1][j]==‘.‘&&a[i-1][j]!=‘.‘&&a[i+2][j]!=‘.‘&&a[i][j-1]!=‘.‘&&a[i+1][j-1]!=‘.‘&&a[i][j+1]!=‘.‘&&a[i+1][j+1]!=‘.‘) return 0; return 1;}int main(){ Rep(i,10) scanf("%s",a[i]+1); Rep(i,10) Rep(j,i) if(a[i][j]!=‘.‘) used[a[i][j]]=true; for(int i=‘A‘;i<=‘L‘;i++) opt[i]=Ret(i); if(!valid()||!DFS(1,1)) puts("No solution"); return 0;}
BZOJ1501 (NOI2005 智慧珠游戏）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。