#include <iostream>
#include <iomanip>
#include <stdlib.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<<" * * * * * * * * 歡迎進入本實驗 * * * * * * * "<<endl;
	int flag=1;
	while(flag=1)
	{
      cout<<endl;
		cout<<"菜單:"<<endl<<"1、實驗說明"<<endl<<"2、開始馬周游問題的求解"<<endl<<"3、退出"<<endl;
		cout<<endl;	cout<<" 請輸入您的選項(1  2  3)    "<<endl;
		int cd;
		cout<<" 您的選項是:   ";
		cin>>cd;
		switch(cd)
		{
		case 1:{
			cout<<"程序功能：實現馬周游棋盤，最后回到起點"<<endl<<"實現方法：回溯法"<<endl;
			cout<<"作者：駱宏峰"<<endl;
			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 p=0,q=0;
    int s[30][30];
    int i,j;
    int w=1;
    int num=0;
    int n;
    cout<<"   輸入棋盤的大小(不大于10):n=";
    cin>>n;
    for(i=0;i<n;++i)
        for(j=0;j<n;j++)
            s[i][j]=88;
    cout<<"  原始棋盤的情況"<<endl;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            cout<<s[i][j]<<" ";
        cout<<endl;
    }
    cout<<"   輸入馬在棋盤中的位置:"<<endl;
    cout<<"x=";
    cin>>p;
    cout<<"y=";
    cin>>q;

    p--;
    q--;
	x=p;
	y=q;
    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||(p-x)*(p-x)+(q-y)*(q-y)!=5);
    
    cout<<"      馬跳之后的情況(數字表示跳躍先后順序)"<<endl;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            cout<<setfill('0')<<setw(2)<<s[i][j]<<" ";
        cout<<endl;
    }
    cout<<"    跳過的路徑一共有"<<m<<"條"<<endl;
    if(m==0)
        cout<<"  不存在合理過程"<<endl;

    cout<<"    一共嘗試過：";
    cout<<num<<" 條路徑"<<endl;

	cout<<endl;
	cout<<endl;
	break;
			   }
	case 3:exit(1);break;
	default:cout<<"選擇錯誤！  請重新選擇！"<<endl;break;
		}
	}
}