「箱入娘」について

箱入娘」について

/*$Id: hakoiri.c,v 1.5 2012/04/08 13:39:48 takeshi Exp takeshi $*/
#include
#include
#include
#define SP ' '
#define UP 0
#define DW 1
#define LF 2
#define RT 3
#define X 5
#define Y 4
#define NN 4
struct brd{
char brd[X][Y],cmp[X][Y]; int ct; struct brd *prv,*nxt,*prt,*l,*r;};
struct brd *c_n,*l_n,*t_n,*st[200]; int ct,ct2,sp;
struct brd top={{"","","","",""},{"","","","",""},0,0,0,0,0,0};
char *bc="1234567890#";
char *c12[NN]={"1346","4580","1347","13"};
char *c11[NN]={"7890","1367","567890#","6890"};
char *c21[NN]={"","","","457"};
int n;
#define N 11
struct sz{int x,y;}; struct po{int i,j;};
struct sz b[NN][N]={
{{1,2},{2,2},{1,2},{1,2},{2,1},{1,2},{1,1},{1,1},{1,1},{1,1}},
{{1,1},{2,2},{1,1},{1,2},{1,2},{1,1},{1,1},{1,2},{2,1},{1,2}},
{{1,2},{2,2},{1,2},{1,2},{1,1},{1,1},{1,2},{1,1},{1,1},{1,1},{1,1}},
{{1,2},{2,2},{1,2},{2,1},{2,1},{1,1},{2,1},{1,1},{1,1},{1,1}}};
struct po p[NN][N]={
{{0,0},{0,1},{0,3},{2,0},{2,1},{2,3},{3,1},{3,2},{4,0},{4,3}},
{{0,0},{0,1},{0,3},{1,0},{1,3},{2,1},{2,2},{3,0},{3,1},{3,3}},
{{0,0},{0,1},{0,3},{2,0},{2,1},{2,2},{2,3},{3,1},{3,2},{4,0},{4,3}},
{{0,0},{0,1},{0,3},{2,0},{2,2},{3,0},{3,1},{3,3},{4,0},{4,3}}};
int bn[NN]={N-1,N-1,N,N-1};
void display(struct brd *x){
char buf1[80],buf2[80];
int i,j;
printf("No:%d\n",x->ct);
for(j=0;jbrd[i][j]!=x->brd[i][j+1])){buf1[4*j+4]='|';buf2[4*j+4]='+';}
if(x->brd[i][j]==SP)buf1[4*j+2]='*';
if((i==X-1)||(x->brd[i][j]!=x->brd[i+1][j])){
buf2[4*j ]='+';buf2[4*j+1]='-'; buf2[4*j+2]='-';buf2[4*j+3]='-';}
}buf1[4*Y+1]='\0';buf2[4*Y]='+';buf2[4*Y+1]='\0';
printf("%s\n",buf1);printf("%s\n",buf2);}}
void cp_brd(struct brd *a,struct brd *r){
int i,j;
for(i=0;ibrd[i][j]=a->brd[i][j];}
void s_blk(struct brd *a,int x,int y,char c,int *k,int *l){
int i,j;
for(i=0;ibrd[i][j]==c){*k=i;*l=j;return;}}
int mv_chk(int op,struct brd *a,int x,int y,char c,int i,int j){
int ret;
switch(op){
case UP:
ret=((i>0)&&(a->brd[i-1][j]==SP)&&((x==1)||(a->brd[i-1][j+1]==SP))); break;
case DW:
ret=((i+ybrd[i+y][j]==SP)&&((x==1)||(a->brd[i+y][j+1]==SP))); break;
case LF:
ret=((j>0)&&(a->brd[i][j-1]==SP)&&((y==1)||(a->brd[i+1][j-1]==SP))); break;
case RT:
ret=((j+xbrd[i][j+x]==SP)&&((y==1)||(a->brd[i+1][j+x]==SP))); break;
default: break;
}return(ret);}
void mv_blk(int op,struct brd *r,int x,int y,char c,int i,int j){
switch(op){
case UP:
r->brd[i-1][j]=c;r->brd[i-1+y][j]=SP;
if(x>1){r->brd[i-1][j+1]=c;r->brd[i-1+y][j+1]=SP;}
break;
case DW:
r->brd[i+y][j]=c; r->brd[i][j]=SP;
if(x>1){r->brd[i+y][j+1]=c;r->brd[i][j+1]=SP;}
break;
case LF:
r->brd[i][j-1]=c; r->brd[i][j-1+x]=SP;
if(y>1){r->brd[i+1][j-1]=c;r->brd[i+1][j-1+x]=SP;}
break;
case RT:
r->brd[i][j+x]=c; r->brd[i][j]=SP;
if(y>1){r->brd[i+1][j+x]=c;r->brd[i+1][j]=SP;}
break;
default: break;}}
struct brd *op_blk(int op,struct brd *a,int x,int y,char c){
int i,j,k,l;
struct brd *r;
s_blk(a,x,y,c,&i,&j);
if(mv_chk(op,a,x,y,c,i,j)){
r=(struct brd *)malloc(sizeof(struct brd));
cp_brd(a,r);
mv_blk(op,r,x,y,c,i,j);
r->ct=a->ct+1;r->prt=a;return r;
}else return 0;}
char chg(char c){
int i;
for(i=0;icmp[i][j]=chg(x->brd[i][j]);
for(i=0;icmp[i][j]>x->cmp[i][Y-1-j])return;
else if(x->cmp[i][j]cmp[i][Y-1-j]){
for(k=0;kcmp[k][l]; x->cmp[k][l]=x->cmp[k][Y-1-l]; x->cmp[k][Y-1-l]=t;
}return;
}}}
int cmp_brd(struct brd *p1,struct brd *p2){
int i,j;
for(i=0;icmp[i][j]>p2->cmp[i][j])return 1;
if(p1->cmp[i][j]cmp[i][j])return -1;
}return 0;}
int chk(struct brd *x){
struct brd *p;
p=t_n;while(p!=0){
switch(cmp_brd(p,x)){
case 0: return 0;
case 1: if(p->r!=0)p=p->r; else {p->r=x;return 1;} break;
case -1: if(p->l!=0)p=p->l; else {p->l=x;return 1;} break;
}}}
void mk_top(int l){
int i,j,k;
top.brd[4][1]=top.brd[4][2]=SP;
for(k=0;k3)n=0;mk_top(n);display(c_n);
while(c_n!=0){
for(i=0;inxt=t;t->prv=l_n;t->nxt=0;t->l=0;t->r=0;l_n=t;ct2++;
if(t->ct!=ct){ct=t->ct;printf("Step:%d:%d\n",ct,ct2);}
if((t->brd[X-1][1]=='2')&&(t->brd[X-1][2]=='2')){
printf("Ans. found\n");
sp=0;while(t!=0){st[sp++]=t;t=t->prt;}
for(sp--;sp>=0;sp--)
{scanf("%c",&c);printf("\x1b[2J");display(st[sp]);}
exit(0);
}
}else free(t);
}c_n=c_n->nxt;
}printf("Fail\n");}


この記事へのコメント

2012年03月15日 03:41
遅いので2分木検索にしました

この記事へのトラックバック