国际象棋，走马遍历问题。利用堆栈实现，模仿MAZE算法，有注释，但是算法不够快，高阶棋盘耗时长.zip

#include<iostream> using namespace std; #define StackSize 100000//最大步数100000步 struct Turn//转向坐标 { int xmove; int ymove; }; struct position { int x; int y; unsigned int order;//位置坐标及其转向 }; Turn Move[9]={{0,0},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2}};//9个方向坐标的变化 class Stacktype//堆栈类 { public: Stacktype(); ~Stacktype(); bool IsEmpty(){return Top==0;}; bool IsFull(){return Top==StackSize;}; void Push(position Item); position Pop(); void PrintPath(); private: position Data[StackSize];//储存走过的路径，最多100000步 int Top;//步数的数量 int Size;//大小 }; Stacktype::Stacktype() { for(int i=0;i<200;i++)//栈的初始化 { Data[i].x=0; Data[i].y=0; Data[i].order=0; } Top=0; Size=StackSize;//步数最大100000步 }; Stacktype::~Stacktype(){};//析构函数 void Stacktype::PrintPath() { cout<<"Path:"<<endl; for( int i=1;i<=Top;i++) cout<<Data[i].x-1<<","<<Data[i].y-1<<"-->"; }; void Stacktype::Push(position Item) { if(IsFull()) cout<<"栈已满！"<<endl; else { Top+=1; Data[Top]=Item; } }; position Stacktype::Pop() { if(IsEmpty()) cout<<"栈已空！"<<endl; else { return Data[Top--]; } }; int main() { int n; cout<<"Please enter the size of the chessboard n(n>=3) : "; cin>>n; while(n<=2) { cout<<"Please enter the CORRECT size of the chessboard n : "; cin>>n; } int line,column;//行和列 line=column=n+4; int ** Mark=new int*[line];//棋盘为二维数组 for(int i=0;i<line;i++) { Mark[i]=new int[column];}//棋盘初始化 for(int j=0;j<line;j++) for(int k=0;k<column;k++) { if((j==0)|(j==1)|(j==line-2)|(j==line-1)) Mark[j][k]=1;//初始化棋盘两层围墙为1 if((k==0)|(k==1)|(k==column-2)|(k==column-1)) Mark[j][k]=1;//初始化棋盘两层围墙为1 } Stacktype Stack;//Stack用来储存路径 int Nextx,Nexty; position CurrentPosition; bool Find; Find=false; int count; cout<<"Please enter the position of the starting place( x , y ):";//x，y为n×n中的位置，x为横坐标(1~n),y为纵坐标(1~n) cin>>CurrentPosition.x>>CurrentPosition.y; //判断位置是否在合理的位置 while((CurrentPosition.x<=0)|(CurrentPosition.x>n)|(CurrentPosition.y<=0)|(CurrentPosition.y>n)) { cout<<"Wrong position ! Please type again"<<endl;//输入坐标不在(1~n)的范围，重新输入 cout<<"( x , y ):"; cin>>CurrentPosition.x>>CurrentPosition.y; } CurrentPosition.x=CurrentPosition.x+1;//坐标转换为带围墙的棋盘Mark上的坐标（0~n+3） CurrentPosition.y=CurrentPosition.y+1; Mark[CurrentPosition.x][CurrentPosition.y]=1; CurrentPosition.order=0; Stack.Push(CurrentPosition); while((!Stack.IsEmpty())&&(!Find))//当栈为空时且标志位为0时表示找不到跳出循环，输出结果 { if(CurrentPosition.order==9) {Mark[CurrentPosition.x][CurrentPosition.y]=0;}//从order=9的位置返回时，将其置为0 CurrentPosition=Stack.Pop();//目前位置等于前一个位置 CurrentPosition.order+=1; while((CurrentPosition.order<=8)&&(!Find))//当order=9时表明无路可走，只能返回，跳出此循环 { Nextx=CurrentPosition.x+Move[CurrentPosition.order].xmove; Nexty=CurrentPosition.y+Move[CurrentPosition.order].ymove; if(Mark[Nextx][Nexty]==0) { Mark[Nextx][Nexty]=1; Stack.Push(CurrentPosition); CurrentPosition.x=Nextx; CurrentPosition.y=Nexty; CurrentPosition.order=0; } CurrentPosition.order+=1; count=0; for(int j=0;j<line;j++) for(int k=0;k<column;k++) {if (Mark[j][k]==1) {count+=1;}} if(count==line*line) Find=1;//如果已经遍历，就将标志置为1 } } if (Find) {Stack.PrintPath();cout<<CurrentPosition.x-1<<","<<CurrentPosition.y-1;} if(!Find) cout<<"Can't find way to cover the whole chessboard."<<endl; }