您好,登錄后才能下訂單哦!
這篇文章主要介紹如何使用C++實(shí)現(xiàn)馬踏棋盤(pán),文中介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們一定要看完!
馬踏棋盤(pán),用1枚馬走遍棋盤(pán)。我用一個(gè)二維數(shù)組記錄模擬的整個(gè)路徑,x為列,y為行,以順時(shí)針的方式尋找下一格,算法比較簡(jiǎn)單,就通過(guò)遞歸和循環(huán)回溯即可,就是如果是8*8的數(shù)組,最壞可能執(zhí)行8^(x*y)次,耗時(shí)長(zhǎng)到懷疑人生。
#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; }
以上是“如何使用C++實(shí)現(xiàn)馬踏棋盤(pán)”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對(duì)大家有幫助,更多相關(guān)知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。