智慧珠游戏拼盘说明书52图解

来源：蜘蛛抓取(WebSpider) 时间：2016-10-07 11:40 标签： 智慧珠游戏拼盘
让慧聪网撮合专家为您解决采购难题
您采购的产品：
请输入采购产品
您的手机号码：
请输入手机号码
提交成功！
电话：6 &&
联系人：余小飞&销售部总监
公司名称：深圳市熙宝生活用品有限公司
期望采购价格 :
请输入期望价格
询价说明 :
请输入正确的11位手机号码
慧聪采购团队会很快与您联系，请保持电话畅通！
成功提交询价单 ，请耐心等待报价
关注后，报价结果将通过微信公众号发送到您的手机 。
热门推荐 ：
按字母分类 ：解题报告（9）
题目描述：一个10*10的直角三角形拼盘，给你12种长得各不相同的奇奇怪怪的零件，要求放入所有零件，刚好覆盖拼盘。
输入：一个拼盘，包括已经放好的零件。
输出：一种覆盖方案。
众所周知，对于这种精确覆盖类型的问题，可以用Knuth神发明的Dancing-Link进行搜索。
在精确覆盖问题中，行表示决策，列表示任务，于是建好模型之后，直接套Dancing-Link模版就行了，搜索效率十分高。
值得一提的是，DL即使效率高，仍然要尽量优化。
这题的一个头疼之处在于不仅要打常量表，还要考虑旋转与翻转，这样一来DL的行数就会较多，上升至5k行左右，跑起来就有些吃力了，会不幸TLE……
解决方法很简单，根据不同的零件的特征，变换时稍微注意判下重就好了，这样所有数据都是秒出结果。
#include&cstdio&
#include&cstring&
const int maxnode=100000;
#define GO(j,s,A) for(j=A[s]; j!=s; j=A[j])
int v[13][5]= {
{0,0,0,0,0},
{0,1,0,0,0},
{0,0,0,0,0},
{0,0,0,1,0},
{0,0,1,1,0},
{0,1,2,2,2},
{0,0,0,0,1},
{0,0,0,1,1},
{0,0,0,1,1},
{0,0,0,1,1},
{0,1,1,1,2},
{0,1,1,2,2},
{0,0,0,0,1}
int w[13][5]= {
{0,0,0,0,0},
{0,0,1,0,0},
{0,1,2,3,0},
{0,1,2,0,0},
{0,1,0,1,0},
{0,0,0,1,2},
{0,1,2,3,1},
{0,1,2,0,2},
{0,1,2,0,1},
{0,1,2,2,3},
{0,-1,0,1,0},
{0,0,1,1,2},
{0,1,2,3,0}
bool rol[13]={0,0,0,1,0,0,1,0,1,1,0,0,1};
char cmd,mep[11][11],tpy[50000];
bool vc[27],vis[11][11],can,br[5];
int i,j,k,q,tm,nx,ny,ar[60];
int U[maxnode],D[maxnode],L[maxnode],R[maxnode],h[maxnode],l[maxnode],la[maxnode],S[100],sz,
int ans[50000],
void addrow(char ttpp)
int i,j, p=0, tmp=0, pz= ht++;
for(i=1,p=0; i&=10; i++)
for(j=1; j&=i; j++)
tmp++, (vis[i][j])? ar[++p]=tmp,br[ht][tmp]=true :0;
ar[++p]=55+(ttpp-'A'+1);
for(i=pz+1; i&= i++)
h[i]=ht, l[i]=ar[i-pz];
L[i]=i-1, R[i]=i+1;
U[i]=la[l[i]], D[la[l[i]]]=i, la[l[i]]=i;
D[i]=l[i], U[l[i]]=i, S[l[i]]++;
L[pz+1]=sz, R[sz]=pz+1;
void Ins()
for(i=1; i&=10; i++)
for(j=1; j&=i; j++)
memset(vis,0,sizeof(vis));
for(q=0; q&5; q++)
nx=i+v[k][q], ny=j+w[k][q];
if(nx&1 || nx&10 || ny&1 || ny&nx) { can= }
else vis[nx][ny]=
else addrow('A'+k-1);
void Rot() {
for(q=0; q&5; q++)
nx=-w[k][q], ny=v[k][q], v[k][q]=nx, w[k][q]=
void Fanx() {
for(q=0; q&5; q++)
v[k][q]*=1, w[k][q]*=-1;
void Fany() {
for(q=0; q&5; q++)
v[k][q]*=-1, w[k][q]*=1;
void MakeMap()
for(i=0,sz=55+12; i&= i++) L[i]=i-1, R[i]=i+1, la[i]=i;
L[0]=sz, R[sz]=0;
for(k=1; k&=12; k++)
Ins(); if(rol[k]){Fanx();Ins();Fanx(); Fany();Ins();Fany();} Rot();
Ins(); if(rol[k]){Fanx();Ins();Fanx(); Fany();Ins();Fany();} Rot();
Ins(); if(rol[k]){Fanx();Ins();Fanx(); Fany();Ins();Fany();} Rot();
Ins(); if(rol[k]){Fanx();Ins();Fanx(); Fany();Ins();Fany();} Rot();
void del(int li)
R[L[li]]=R[li], L[R[li]]=L[li];
GO(i,li,D)
D[U[j]]=D[j], U[D[j]]=U[j], S[l[j]]--;
void rel(int li)
GO(i,li,U)
D[U[j]]=j, U[D[j]]=j, S[l[j]]++;
R[L[li]]=li, L[R[li]]=
bool DFS(int d)
if(!R[0]) { atop=d; }
int c=R[0], i,j;
GO(i,0,R) if(S[i]&S[c]) c=i;
ans[d]=h[i];
GO(j,i,R) del(l[j]);
if(DFS(d+1))
GO(j,i,L) rel(l[j]);
int main()
MakeMap();
for(i=1; i&=10; i++)
for(j=1; j&=i; j++)
do{cmd=getchar();}while(cmd=='\n');
if(cmd=='.')
else del(i*(i-1)/2+j);
mep[i][j]=cmd, cmd-='A'-1;
if(!vc[cmd]) { vc[cmd]= del(55+cmd); }
if(DFS(1))
for(k=1; k&= k++)
for(i=1,q=0; i&=10; i++)
for(j=1; j&=i; j++)
if(br[ans[k]][q])
mep[i][j]=tpy[ans[k]];
for(i=1; i&=10; i++)
for(j=1; j&=i; j++) printf(&%c&, mep[i][j]);
printf(&\n&);
else printf(&No solution&);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：13209次
排名：千里之外
原创：16篇

我要回帖

更多关于 智慧珠游戏拼盘 的文章

 

随机推荐