如何使用C++实现马踏棋盘

如何使用C++实现马踏棋盘

这篇文章主要介绍如何使用C++实现马踏棋盘，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

马踏棋盘，用1枚马走遍棋盘。我用一个二维数组记录模拟的整个路径，x为列，y为行，以顺时针的方式寻找下一格，算法比较简单，就通过递归和循环回溯即可，就是如果是8*8的数组，最坏可能执行8^(x*y)次，耗时长到怀疑人生。

#include<iostream>#defineX5#defineY5voidShowResult();usingnamespacestd;intchess[Y][X]={0};intcounter=0;intNext(int*x,int*y,intwhere){switch(where){case0:if(*x+1<X&&*y-2>=0&&chess[*y-2][*x+1]==0){*x+=1;*y-=2;return1;}break;case1:if(*x+2<X&&*y-1>=0&&chess[*y-1][*x+2]==0){*x+=2;*y-=1;return1;}break;case2:if(*x+2<X&&*y+1<Y&&chess[*y+1][*x+2]==0){*x+=2;*y+=1;return1;}break;case3:if(*x+1<X&&*y+2<Y&&chess[*y+2][*x+1]==0){*x+=1;*y+=2;return1;}break;case4:if(*x-1>=0&&*y+2<Y&&chess[*y+2][*x-1]==0){*x-=1;*y+=2;return1;}break;case5:if(*x-2>=0&&*y+1<Y&&chess[*y+1][*x-2]==0){*x-=2;*y+=1;return1;}break;case6:if(*x-2>=0&&*y-1>=0&&chess[*y-1][*x-2]==0){*x-=2;*y-=1;return1;}break;case7:if(*x-1>=0&&*y-2>=0&&chess[*y-2][*x-1]==0){*x-=1;*y-=2;return1;}break;}return0;}intExplore(intx,inty){intx1=x;inty1=y;intflag;intwhere=0;counter++;chess[y][x]=counter;if(counter==X*Y){return1;}flag=Next(&x1,&y1,where);while(flag==0&&where<7){where++;flag=Next(&x1,&y1,where);}while(flag){if(Explore(x1,y1)==1){return1;}else{x1=x;y1=y;where++;flag=Next(&x1,&y1,where);while(flag==0&&where<7){where++;flag=Next(&x1,&y1,where);}}}if(flag==0){chess[y][x]=0;counter--;}return0;}voidShowResult(){for(inti=0;i<Y;i++){for(intj=0;j<X;j++){cout.width(4);cout<<chess[i][j]<<'';}cout<<endl;}cout<<endl;}intmain(){intstart=clock();intresult=Explore(2,1);intend=clock();if(result){ShowResult();}else{cout<<"havenopath！"<<endl;}cout<<"spendtime："<<(end-start)/CLOCKS_PER_SEC<<"s"<<endl;return0;}

以上是“如何使用C++实现马踏棋盘”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注恰卡编程网行业资讯频道！