马的遍历棋盘C语言源码

#define Max 1000 #include"stdio.h" #include"iostream.h" #include"stdlib.h" typedef struct Pos { int x; int y; }Pos; typedef struct Step { int way; int nextNum; }Step; int M=8,N=8; int NextStep[8][2]={{1,2},{2,1},{2,-1},{-1,2},{-2,-1},{-1,-2},{-2,1},{1,-2}}; int over=0; int ChessBoard[Max][Max]={0}; Pos Initial; Pos Way[Max][Max]; bool Valid(Pos p) { if(p.x<0 || p.y<0 || p.x>M-1 || p.y>N-1 || ChessBoard[p.x][p.y]!=0) { return false; } else { return true; } } int Compare(const void *a,const void *b) { Step *m,*n; m=(Step *)a; n=(Step *)b; if(m->way>n->way) { return 1; } else if(m->way==n->way) { return 0; } else return -1; } int CountWay(Pos p) { int count=0; Pos buff; for(int i=0;i<8;i++) { buff.x=p.x+NextStep[i][0]; buff.y=p.y+NextStep[i][1]; if(Valid(buff)) { count++; } } return count; } void Output(Pos p) { int count = M*N-1; int x,y,x1,y1; x=Way[Initial.x][Initial.x].x; y=Way[Initial.x][Initial.y].y; if(over) { printf("Solution is as follows:\n"); printf("Step# %3d: {%2d,%2d}\n",M*N-1-count,p.x,p.y); while(count--) { printf("Step# %3d: {%2d,%2d}\n",M*N-1-count,x,y); x1=x; y1=y; x=Way[x1][y1].x; y=Way[x1][y1].y; } printf("Step# %3d: {%2d,%2d}\n",M*N,p.x,p.y); } else { printf("No Solution"); } } void TraverseChessBoard(Pos& Position,int count) { Pos buff; Step List[8]; int i,j,k; if(count>=M*N) { for(i=0;i<8;i++) { buff.x=Position.x+NextStep[i][0]; buff.y=Position.y+NextStep[i][1]; if(buff.x==Initial.x && buff.y==Initial.y) { Way[Position.x][Position.y]=buff; printf("The feasible modus is as follow:"); printf("The ChessBoard:\n"); for(k=0;k<M;k++) { for(j=0;j<N;j++) { printf("%3d ",ChessBoard[k][j]); } printf("\n"); } over=1; } } return; } else { int num=0; for(i=0;i<8;i++) { buff.x=Position.x+NextStep[i][0]; buff.y=Position.y+NextStep[i][1]; if(Valid(buff)) { List[num].nextNum=i; List[num].way=CountWay(buff); num++;//下一步可以走的点数 } } qsort(List,num,sizeof(Step),Compare); for(i=0; !over && i<num;i++) { int next=List[i].nextNum; buff.x=Position.x+NextStep[next][0]; buff.y=Position.y+NextStep[next][1]; ChessBoard[buff.x][buff.y]=count+1; Way[Position.x][Position.y]=buff; TraverseChessBoard(buff,count+1);//下一点 ChessBoard[buff.x][buff.y]=0;//回溯 } } } int main() { bool f1=false,f2=true,f3=true; printf("please enter the size of the chess board!\n"); printf("M:"); scanf("%d",&M); printf("\n"); printf("N:"); scanf("%d",&N); printf("\n"); //对棋盘的限制条件 if ( ( M != 1&&M != 2&&M != 4 && N != 1 && N != 2 && N!= 4) && ( M%2 == 0 || N%2 == 0 ) ) f1 = true; if ( M== 3 ) { if (N == 4 || N == 6 || N == 8 ) f2 = false; } if (N == 3) { if (M == 4 || M == 6 || M == 8 ) f3 = false; } //初始化起点 Initial.x=M/2; Initial.y=N/2; if(f1 && f2 && f3) { ChessBoard[Initial.x][Initial.y]=1; TraverseChessBoard(Initial,1); Output( Initial ); } return 0; }