- #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]=='o'&&kmq[i][j+1]=='o'&&kmq[i][j+2]=='.')
- return true;
- else if((di==1)&&(kmq[i][j]=='o')&&(kmq[i+1][j]=='o')&&(kmq[i+2][j]=='.'))
- return true;
- else if((di==2)&&(kmq[i][j]=='o')&&(kmq[i-1][j]=='o')&&(kmq[i-2][j]=='.'))
- return true;
- else if((di==3)&&(kmq[i][j]=='o')&&(kmq[i][j-1]=='o')&&(kmq[i][j-2]=='.'))
- return true;
- else
- return false;
- }
- void move(char kmq[5][5],int i,int j,int di){
- if(di==0){
- kmq[i][j]='.';
- kmq[i][j+1]='.';
- kmq[i][j+2]='o';
- }
- if(di==1){
- kmq[i][j]='.';
- kmq[i+1][j]='.';
- kmq[i+2][j]='o';
- }
- if(di==2){
- kmq[i][j]='.';
- kmq[i-1][j]='.';
- kmq[i-2][j]='o';
- }
- if(di==3){
- kmq[i][j]='.';
- kmq[i][j-1]='.';
- kmq[i][j-2]='o';
- }
- }
- void back(char kmq[5][5],int i,int j,int di){
- if(di==0){
- kmq[i][j]='o';
- kmq[i][j+1]='o';
- kmq[i][j+2]='.';
- }
- if(di==1){
- kmq[i][j]='o';
- kmq[i+1][j]='o';
- kmq[i+2][j]='.';
- }
- if(di==2){
- kmq[i][j]='o';
- kmq[i-1][j]='o';
- kmq[i-2][j]='.';
- }
- if(di==3){
- kmq[i][j]='o';
- kmq[i][j-1]='o';
- kmq[i][j-2]='.';
- }
- }
- 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]='.';
- b[(*((*s).base)).seat.i][(*((*s).base)).seat.j+1]='.';
- b[(*((*s).base)).seat.i][(*((*s).base)).seat.j+2]='o';
- }
- if((*((*s).base)).di==1){
- b[(*((*s).base)).seat.i][(*((*s).base)).seat.j]='.';
- b[(*((*s).base)).seat.i+1][(*((*s).base)).seat.j]='.';
- b[(*((*s).base)).seat.i+2][(*((*s).base)).seat.j]='o';
- }
- if((*((*s).base)).di==2){
- b[(*((*s).base)).seat.i][(*((*s).base)).seat.j]='.';
- b[(*((*s).base)).seat.i-1][(*((*s).base)).seat.j]='.';
- b[(*((*s).base)).seat.i-2][(*((*s).base)).seat.j]='o';
- }
- if((*((*s).base)).di==3){
- b[(*((*s).base)).seat.i][(*((*s).base)).seat.j]='.';
- b[(*((*s).base)).seat.i][(*((*s).base)).seat.j-1]='.';
- b[(*((*s).base)).seat.i][(*((*s).base)).seat.j-2]='o';
- }
- 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]=='o')
- k++;
- }
- }
- if(k==1&&kmq[2][2]=='o')
- 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");
- }
- //该片段来自于http://www.codesnippet.cn/detail/100520133269.html
来源: http://www.codesnippet.cn/detail/100520133269.html