如何使用C++实现马踏棋盘
导读:本文共1338字符,通常情况下阅读需要4分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 马踏棋盘,用1枚马走遍棋盘。我用一个二维数组记录模拟的整个路径,x为列,y为行,以顺时针的方式寻找下一格,算法比较简单,就通过递归和循环回溯即可,就是如果是8*8的数组,最坏可能执行8^(x*y)次,耗时长到怀疑人生。#include<iostream>#defineX5#defineY5voidShowResult();usingname... ...
音频解说
目录
(为您整理了一些要点),点击可以直达。马踏棋盘,用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;}
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
本文:
如何使用C++实现马踏棋盘的详细内容,希望对您有所帮助,信息来源于网络。