5*5孔明棋解法代码,C代码库,德仔网

代码语言
代码分类
【C】 5*5孔明棋解法
作者: / 发布于2014/5/22/ 599
5*5孔明棋解法

	#include<stdio.h>
	#include<stdlib.h>
	typedef struct{
	 int i;
	 int j;
	}pos;//棋子位置
	typedef struct{
	 int ord;//移棋序号
	 pos seat;//当前棋子位置
	 int di;//移棋方向，0，1，2，3代表四个方向，右下上左
	}movestep;
	typedef struct{
	 movestep *base;
	 movestep *top;
	 int stacksize;
	}sqstack;

	char kmq[5][5],b[5][5];
	movestep *e=(movestep *)malloc(sizeof(movestep));
	sqstack *s=(sqstack *)malloc(sizeof(sqstack));

	bool pass(char kmq[5][5],int i,int j,int di){
	 if(di==0&&kmq[i][j]==&apos;o&apos;&&kmq[i][j+1]==&apos;o&apos;&&kmq[i][j+2]==&apos;.&apos;)
	 return true;
	 else if((di==1)&&(kmq[i][j]==&apos;o&apos;)&&(kmq[i+1][j]==&apos;o&apos;)&&(kmq[i+2][j]==&apos;.&apos;))
	 return true;
	 else if((di==2)&&(kmq[i][j]==&apos;o&apos;)&&(kmq[i-1][j]==&apos;o&apos;)&&(kmq[i-2][j]==&apos;.&apos;))
	 return true;
	 else if((di==3)&&(kmq[i][j]==&apos;o&apos;)&&(kmq[i][j-1]==&apos;o&apos;)&&(kmq[i][j-2]==&apos;.&apos;))
	 return true;
	 else
	 return false;
	}
	void move(char kmq[5][5],int i,int j,int di){
	 if(di==0){
	 kmq[i][j]=&apos;.&apos;;
	 kmq[i][j+1]=&apos;.&apos;;
	 kmq[i][j+2]=&apos;o&apos;;
	 }
	 if(di==1){
	 kmq[i][j]=&apos;.&apos;;
	 kmq[i+1][j]=&apos;.&apos;;
	 kmq[i+2][j]=&apos;o&apos;;
	 }
	 if(di==2){
	 kmq[i][j]=&apos;.&apos;;
	 kmq[i-1][j]=&apos;.&apos;;
	 kmq[i-2][j]=&apos;o&apos;;
	 }
	 if(di==3){
	 kmq[i][j]=&apos;.&apos;;
	 kmq[i][j-1]=&apos;.&apos;;
	 kmq[i][j-2]=&apos;o&apos;;
	 }
	}
	void back(char kmq[5][5],int i,int j,int di){
	 if(di==0){
	 kmq[i][j]=&apos;o&apos;;
	 kmq[i][j+1]=&apos;o&apos;;
	 kmq[i][j+2]=&apos;.&apos;;
	 }
	 if(di==1){
	 kmq[i][j]=&apos;o&apos;;
	 kmq[i+1][j]=&apos;o&apos;;
	 kmq[i+2][j]=&apos;.&apos;;
	 }
	 if(di==2){
	 kmq[i][j]=&apos;o&apos;;
	 kmq[i-1][j]=&apos;o&apos;;
	 kmq[i-2][j]=&apos;.&apos;;
	 }
	 if(di==3){
	 kmq[i][j]=&apos;o&apos;;
	 kmq[i][j-1]=&apos;o&apos;;
	 kmq[i][j-2]=&apos;.&apos;;
	 }
	}
	void initstack(sqstack *s){
	 (*s).base=(movestep *)malloc(100*sizeof(movestep));
	 if(!(*s).base)
	 exit(1);
	 (*s).top=(*s).base;
	 (*s).stacksize=100;
	}
	void pop(sqstack *s,movestep *e){
	 if((*s).top==(*s).base)
	 exit(1);
	 *e=* --(*s).top;
	}
	void printstack(sqstack *s){
	 int m=0,n=0;
	 for(;((*s).top)!=(*s).base;(*s).base++){
	 printf("step %d :\\n",(*((*s).base)).ord);
	 if((*((*s).base)).di==0){
	 b[(*((*s).base)).seat.i][(*((*s).base)).seat.j]=&apos;.&apos;;
	 b[(*((*s).base)).seat.i][(*((*s).base)).seat.j+1]=&apos;.&apos;;
	 b[(*((*s).base)).seat.i][(*((*s).base)).seat.j+2]=&apos;o&apos;;
	 }
	 if((*((*s).base)).di==1){
	 b[(*((*s).base)).seat.i][(*((*s).base)).seat.j]=&apos;.&apos;;
	 b[(*((*s).base)).seat.i+1][(*((*s).base)).seat.j]=&apos;.&apos;;
	 b[(*((*s).base)).seat.i+2][(*((*s).base)).seat.j]=&apos;o&apos;;
	 }
	 if((*((*s).base)).di==2){
	 b[(*((*s).base)).seat.i][(*((*s).base)).seat.j]=&apos;.&apos;;
	 b[(*((*s).base)).seat.i-1][(*((*s).base)).seat.j]=&apos;.&apos;;
	 b[(*((*s).base)).seat.i-2][(*((*s).base)).seat.j]=&apos;o&apos;;
	 }
	 if((*((*s).base)).di==3){
	 b[(*((*s).base)).seat.i][(*((*s).base)).seat.j]=&apos;.&apos;;
	 b[(*((*s).base)).seat.i][(*((*s).base)).seat.j-1]=&apos;.&apos;;
	 b[(*((*s).base)).seat.i][(*((*s).base)).seat.j-2]=&apos;o&apos;;
	 }
	 for(m=0;m<=4;m++){
	 for(n=0;n<=4;n++)
	 printf("%c",b[m][n]);
	 printf("\\n");
	 }
	 printf("\\n");
	 }
	}

	void push(sqstack *s,movestep *e){
	 if((*s).top-(*s).base>=((*s).stacksize)){
	 (*s).base=(movestep *)realloc((*s).base,((*s).stacksize+100)*sizeof(movestep));
	 if(!(*s).base)
	 exit(1);
	 (*s).top=(*s).base+(*s).stacksize;
	 (*s).stacksize+=100;
	 }
	 *(*s).top++=*e;
	}
	bool victory(char kmq[5][5]){
	 int i=0,j=0,k=0;
	 for(i=0;i<=4;i++){
	 for(j=0;j<=4;j++){
	 if(kmq[i][j]==&apos;o&apos;)
	 k++;
	 }
	 }
	 if(k==1&&kmq[2][2]==&apos;o&apos;)
	 return 1;
	 else
	 return 0;
	}
	bool stackempty(sqstack *s){
	 if((*s).base==(*s).top)
	 return 1;
	 else
	 return 0;
	}

	int kongmingqi(char kmq[5][5]){
	 int curi=0,curj=0,curdi=0,curstep=1;
	 int i,j,di;
	 do{
	 int flag=0;
	 for(i=curi;((i<=4)&&(!flag));i++){
	 for(j=curj;((j<=4)&&(!flag));j++){
	 for(di=curdi;((di<=3)&&(!flag));di++){
	 if(pass(kmq,i,j,di)){//判断是否能移动
	 move(kmq,i,j,di);//移动棋子
	 (*e).ord=curstep;
	 (*e).seat.i=i;
	 (*e).seat.j=j;
	 (*e).di=di;
	 push(s,e);//移棋步骤进栈
	 if(victory(kmq)){
	 printstack(s);
	 return 1;
	 }
	 curstep++;
	 flag=1;
	 }
	 curdi=0;//重置方向
	 }
	 curj=0;//重置位置
	 }
	 curi=0;
	 }
	 if(flag==0)
	 if(!stackempty(s)){
	 pop(s,e);//出栈
	 back(kmq,(*e).seat.i,(*e).seat.j,(*e).di);//撤棋
	 curstep--;
	 curi=(*e).seat.i;
	 curj=(*e).seat.j;
	 curdi=(*e).di+1;
	 }
	 }while(!stackempty(s));
	 return 0;
	}
	void main(){
	 initstack(s);
	 int i;
	 int j;
	 char a[5][5];
	 for(i=0;i<=4;i++)
	 for(j=0;j<=4;j++)
	 scanf("%c",&a[i][j]);
	 for(i=0;i<=4;i++){
	 for(j=0;j<=4;j++){
	 kmq[i][j]=a[i][j];
	 b[i][j]=a[i][j];
	 }
	 printf("\\n");
	 }
	 if(kongmingqi(kmq)==1)
	 printf("\\n there is an answer");
	 else
	 printf("there is no answer!");
	 system("pause");
	}
试试其它关键字
　孔明棋　
同语言下
可能有用的
贡献的其它代码Label