求助遍历棋盘
马踏棋盘程序代码:
#include <stdio.h> #include <stdlib.h> typedef struct //结点类型 { int num1; int num2; struct node *prior; struct node *next; }node; typedef struct //走法数组类型 { int m; int n; }array; typedef struct //栈的类型 { int row; int col; }stack; int main() { int i,j,k,l; int a,b=0; node *head,*p,*ptr; int flag[9][9]={0}; array po[9]; stack S[65]; //初始化栈 int top=0; S[0].row=S[0].col=0; head=(node *)malloc(sizeof(node)); //初始化链表 head->num1=head->num2=NULL; head->prior=NULL; head->next=NULL; p=head; printf("请输入起点坐标:i,j\n"); scanf("%d,%d",&i,&j); top++; S[top].row=i; //已遍历方格入栈 S[top].col=j; flag[i][j]=1; //标记遍历方格 ptr=(node *)malloc(sizeof(node)); //建立表头结点 ptr->num1=i; ptr->num2=j; ptr->prior=p; ptr->next=NULL; p=ptr; do { if(top==50) { printf("hahah\n"); } printf("%d,%d->",S[top].row,S[top].col); for(k=1;k<9;k++) //8种走法 { if(k==1||k==2) po[k].m=i-1; if(k==3||k==4) po[k].m=i+1; if(k==5||k==6) po[k].m=i-2; if(k==7||k==8) po[k].m=i+2; if(k==1||k==3) po[k].n=j-2; if(k==2||k==4) po[k].n=j+2; if(k==5||k==7) po[k].n=j-1; if(k==6||k==8) po[k].n=j+1; } if((a!=0)&&(b!=0)) //发生回溯的情况 { for(k=1;k<9;k++) { if((po[k].m==a)&&(po[k].n==b)) {a=0; b=0; for(l=1;l<(k+1);l++) { po[l].m=0; po[l].n=0; } break; } } } for(k=1;k<9;k++) //筛选不可行走法 { if((po[k].m<1)||(po[k].m>8)||(po[k].n<1)||(po[k].n>8)) {po[k].m=0; po[k].n=0;} if(flag[po[k].m][po[k].n]==1) {po[k].m=0; po[k].n=0;} } for(k=1;k<9;k++) { if(flag[po[k].m][po[k].n]==0&&po[k].m!=0) { top++; i=po[k].m; j=po[k].n; S[top].row=i; S[top].col=j; flag[i][j]=1; ptr=(node *)malloc(sizeof(node)); ptr->num1=i; ptr->num2=j; ptr->prior=p; ptr->next=NULL; p=ptr; break; } } if(k==9) //当无可行路径时,回溯 { a=i; b=j; flag[i][j]=0; p=p->prior; free(ptr); ptr=p; top--; if(top==0) { printf("\n无法遍历棋盘!\n"); system("pause"); return 0; } i=S[top].row; j=S[top].col; } }while(0<top<65); if(top==64) { ptr->next=NULL; p=head; for(l=1;l<64;l++) { p=p->next; printf("(%d,%d)",p->num1,p->num2); } } system("pause"); return 0; }
回溯的代码是不是有问题,好像会出现重复的情况,得不出结果
用这种方式能解决问题吗 可以改出来吗