#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>
using namespace std;
inline int good(int x,int y,int s[30][30],int n)
{
    if(x>=0&&x<=n-1&&y>=0&&y<=n-1&&s[y][x]==88)
        return 1;
    else
        return 0;
}


void main()
{
		cout<<" * * * * * * * * 歡迎進(jìn)入本實(shí)驗(yàn) * * * * * * * "<<endl;
	int flag=1;
	while(flag=1)
	{
      cout<<endl;
		cout<<"     菜單:  1、實(shí)驗(yàn)說(shuō)明    2、開(kāi)始馬周游問(wèn)題的求解  3、退出  "<<endl;
		cout<<endl;	cout<<"      請(qǐng)輸入您的選項(xiàng)(1  2  3   )    "<<endl;
		int cd;
		cout<<"    您的選項(xiàng)是:   ";
		cin>>cd;
		switch(cd)
		{
		case 1:{ break;}
		case 2:{
    enum road{d11,d12,d21,d22,d31,d32,d41,d42};
    road d[100];
    int m=0;
    int x=0,y=0;
    int s[30][30];
    int i,j;
    int w=1;
    int num=0;
    int n;
    cout<<"   輸入棋盤(pán)的大小:n=";
    cin>>n;
    for(i=0;i<n;++i)
        for(j=0;j<n;j++)
            s[i][j]=88;
    cout<<"  原始棋盤(pán)的情況"<<endl;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            cout<<s[i][j]<<" ";
        cout<<endl;
    }
    cout<<"   輸入馬在棋盤(pán)中的位置:"<<endl;
    cout<<"x=";
    cin>>x;
    cout<<"y=";
    cin>>y;
	 SYSTEMTIME st;
	GetLocalTime(&st);

 int b;
 b=st.wSecond*1000+st.wMilliseconds;
    x--;
    y--;
    d[0]=d11;
    s[y][x]=1;
    do{
        if(d[m]==d11&&good(x+1,y-2,s,n)){x++;y=y-2;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d12&&good(x+2,y-1,s,n)){x=x+2;y--;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d21&&good(x+2,y+1,s,n)){x=x+2;y++;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d22&&good(x+1,y+2,s,n)){x++;y=y+2;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d31&&good(x-1,y+2,s,n)){x--;y=y+2;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d32&&good(x-2,y+1,s,n)){x=x-2;y++;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d41&&good(x-2,y-1,s,n)){x=x-2;y--;d[++m]=d11;s[y][x]=++w;num++;}
        else if(d[m]==d42&&good(x-1,y-2,s,n)){x--;y=y-2;d[++m]=d11;s[y][x]=++w;num++;}
        else{
            while(d[m]==d42){
                m--;
                if(d[m]==d11){s[y][x]=88;w--;x--;y=y+2;}
                if(d[m]==d12){s[y][x]=88;w--;x=x-2;y++;}
                if(d[m]==d21){s[y][x]=88;w--;x=x-2;y--;}
                if(d[m]==d22){s[y][x]=88;w--;x--;y=y-2;}
                if(d[m]==d31){s[y][x]=88;w--;x++;y=y-2;}
                if(d[m]==d32){s[y][x]=88;w--;x=x+2;y--;}
                if(d[m]==d41){s[y][x]=88;w--;x=x+2;y++;}
                if(m!=0&&d[m]==d42){s[y][x]=88;w--;x++;y=y+2;}
            }
            d[m]=road(d[m]+1);
        }
    }while((m!=0||d[0]!=d42||good(x-1,y-2,s,n))&&m!=n*n-1);
		GetLocalTime(&st);

 int a;
 a=st.wSecond*1000+st.wMilliseconds;
    
    cout<<"      馬跳之后的情況(數(shù)字表示跳躍先后順序)"<<endl;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            cout<<setfill('0')<<setw(2)<<s[i][j]<<" ";
        cout<<endl;
    }

    cout<<"    跳過(guò)的路徑一共有"<<m<<"條"<<endl;
    if(m==0)
        cout<<"  不存在合理過(guò)程"<<endl;
    if(m==n*n-1)
        cout<<"   存在一種合理過(guò)程"<<endl;
    cout<<"    一共嘗試過(guò)：";
    cout<<num<<" 條路徑"<<endl;
	cout<<"   共花時(shí)間為:  "<<a-b<<"毫秒  "<<endl;
	cout<<endl;
	cout<<endl;
	break;
			   }
	case 3:exit(1);break;
	default:cout<<"選擇錯(cuò)誤！  請(qǐng)重新選擇！"<<endl;break;
		}

	}

}