C++實現(xiàn)馬踏棋盤(騎士周游)

更新時間：2022年02月15日 11:41:10 作者：lld951027

這篇文章主要為大家詳細介紹了C++實現(xiàn)馬踏棋盤，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

馬踏棋盤，用1枚馬走遍棋盤。我用一個二維數(shù)組記錄模擬的整個路徑，x為列，y為行，以順時針的方式尋找下一格，算法比較簡單，就通過遞歸和循環(huán)回溯即可，就是如果是8*8的數(shù)組，最壞可能執(zhí)行8^(x*y)次，耗時長到懷疑人生。

#include<iostream>
#define X 5
#define Y 5
?
void ShowResult();
using namespace std;
?
int chess[Y][X]={
?? ?0
};
int counter=0;
?
int Next(int* x,int* y,int where){
?
?? ?switch(where){
?? ??? ?case 0:
?? ??? ??? ?if(*x+1<X&&*y-2>=0&&chess[*y-2][*x+1]==0){
?? ??? ??? ??? ?*x+=1;
?? ??? ??? ??? ?*y-=2;
?? ??? ??? ??? ?return 1;
?? ??? ??? ?}
?? ??? ??? ?break;
?? ??? ?case 1:
?? ??? ??? ?if(*x+2<X&&*y-1>=0&&chess[*y-1][*x+2]==0){
?? ??? ??? ??? ?*x+=2;
?? ??? ??? ??? ?*y-=1;
?? ??? ??? ??? ?return 1;
?? ??? ??? ?}
?? ??? ??? ?break;
?? ??? ?case 2:
?? ??? ??? ?if(*x+2<X&&*y+1<Y&&chess[*y+1][*x+2]==0){
?? ??? ??? ??? ?*x+=2;
?? ??? ??? ??? ?*y+=1;
?? ??? ??? ??? ?return 1;
?? ??? ??? ?}
?? ??? ??? ?break;
?? ??? ?case 3:
?? ??? ??? ?if(*x+1<X&&*y+2<Y&&chess[*y+2][*x+1]==0){
?? ??? ??? ??? ?*x+=1;
?? ??? ??? ??? ?*y+=2;
?? ??? ??? ??? ?return 1;
?? ??? ??? ?}
?? ??? ??? ?break;
?? ??? ?case 4:
?? ??? ??? ?if(*x-1>=0&&*y+2<Y&&chess[*y+2][*x-1]==0){
?? ??? ??? ??? ?*x-=1;
?? ??? ??? ??? ?*y+=2;
?? ??? ??? ??? ?return 1;
?? ??? ??? ?}
?? ??? ??? ?break;
?? ??? ?case 5:
?? ??? ??? ?if(*x-2>=0&&*y+1<Y&&chess[*y+1][*x-2]==0){
?? ??? ??? ??? ?*x-=2;
?? ??? ??? ??? ?*y+=1;
?? ??? ??? ??? ?return 1;
?? ??? ??? ?}
?? ??? ??? ?break;
?? ??? ?case 6:
?? ??? ??? ?if(*x-2>=0&&*y-1>=0&&chess[*y-1][*x-2]==0){
?? ??? ??? ??? ?*x-=2;
?? ??? ??? ??? ?*y-=1;
?? ??? ??? ??? ?return 1;
?? ??? ??? ?}
?? ??? ??? ?break;
?? ??? ?case 7:
?? ??? ??? ?if(*x-1>=0&&*y-2>=0&&chess[*y-2][*x-1]==0){
?? ??? ??? ??? ?*x-=1;
?? ??? ??? ??? ?*y-=2;
?? ??? ??? ??? ?return 1;
?? ??? ??? ?}
?? ??? ??? ?break;
?? ?}
?? ?return 0;
}
?
int Explore(int x,int y){
?? ?int x1=x;
?? ?int y1=y;
?? ?int flag;
?? ?int where=0;
?? ?
?
?? ?counter++;
?? ?chess[y][x]=counter;
?? ?
?
?? ?if(counter==X*Y){
?? ??? ?return 1;
?? ?}
?? ?
?? ?
?? ?
?? ?flag=Next(&x1,&y1,where);
?? ?while(flag==0&&where<7){
?? ??? ?where++;
?? ??? ?flag=Next(&x1,&y1,where);
?? ?}
?? ?
?? ?
?? ?while(flag){
?? ??? ?if(Explore(x1,y1)==1){
?? ??? ??? ?return 1;
?? ??? ?}
?? ??? ?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--;
?? ?}
?? ?return 0;
}
?
void ShowResult(){
?? ?
?? ?for(int i=0;i<Y;i++){
?? ??? ?for(int j=0;j<X;j++){
?? ??? ??? ?cout.width(4);
?? ??? ??? ?cout<<chess[i][j]<<' ';
?? ??? ?}
?? ??? ?cout<<endl;
?? ?}
?? ?cout<<endl;
}
?
int main(){
?? ?int start=clock();
?? ?int result=Explore(2,1);
?? ?int end=clock();
?? ?if(result){
?? ??? ?ShowResult();?? ??? ?
?? ?}
?? ?else{
?? ??? ?cout<<"have no path！"<<endl;?
?? ?}
?
?? ?cout<<"spend time："<<(end-start)/CLOCKS_PER_SEC<<" s"<<endl;
?? ?return 0;
}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: