BZOJ1501 (NOI2005 智慧珠游戏） - c++编程基础

TOP

BZOJ1501 (NOI2005 智慧珠游戏）(一)

2015-07-20 17:32:06 来源: 作者: 【大中小】浏览:9次

Tags：BZOJ1501 NOI2005 智慧游戏

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

BKK

BJKK

JJJDD

GJGDDC

GGGCCCI

EEEHHIIA

ELHHHIAAF

ELLLLIFFFF

HINT

Source

Dance Link

恩一道非常恶心的搜索题，不过没学dancing Links所以这题的剪枝是抄别人开头的可行性剪枝。。

复制代码

#include

using namespace std;

const int N = 150;

#define rep(i,n) for(int i=0;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[

首页上一页 1 2 3 下一页尾页 1/3/3
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：SICP 习题（2.8）解题总结：区..	下一篇：自定义circle

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: