//馬踏棋盤
//運算速度有待提高，其次位置最好設在(0 0)

#include <iostream.h>
#include <stdio.h>

#define RANGE 7						//RANGE=棋盤大小-1
#define SQUARE (RANGE+1)*(RANGE+1)
#define MAX SQUARE+1

const short int gostep[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};

struct BASE
{
	short int x,y,ex;
};

class HOUSE
{
private:
	BASE infor[MAX];
	short int point;
	short int prt[RANGE+1][RANGE+1];

public:
void input()
{
short int startx,starty,i;
	cout<<"請輸入開始位置x y（用空格分開）"<<RANGE+1<<"×"<<RANGE+1<<"：";
	cin>>startx>>starty;
	infor[0].x=startx;
	infor[0].y=starty;
	infor[0].ex=0;
	point=0;
	for (i=1; i<=MAX-1; i++)
	{
	infor[i].x=0;
	infor[i].y=0;
	infor[0].ex=0;
	}
}

int findway()
{
short int pt,nextx,nexty,i,j;
	point=0;
	for(i=0; i<RANGE+1; i++)
		for(j=0; j<RANGE+1; j++) prt[i][j]=0;
	prt[infor[0].x][infor[0].y]=1;
	do
	{
		if (point<0) 
			return 0;
		pt=point;
		while(infor[pt].ex<8)
		{
			nextx=infor[pt].x+gostep[infor[pt].ex][0];
			nexty=infor[pt].y+gostep[infor[pt].ex][1];
			infor[pt].ex++;
			
			if ((prt[nextx][nexty]==0)&&(nextx>=0)&&(nexty>=0)&&(nextx<=RANGE)&&(nexty<=RANGE))
			{				
				point++;
				infor[point].x=nextx;
				infor[point].y=nexty;				
				infor[point].ex=0;
				prt[nextx][nexty]=prt[infor[pt].x][infor[pt].y]+1;				
				if (prt[nextx][nexty]>=SQUARE) 
					return 1;
				break;
			}
		}
		if (infor[point].ex>7) 
		{prt[infor[point].x][infor[point].y]=0; point--; }
	}
	while(1);
	return 0;
}

void print()
{
short int i,j;
if (point>0)
{
	for(j=0; j<RANGE+1; j++)
	{
		for(i=0; i<RANGE+1; i++)
		{
			cout<<(prt[j][i])<<"  ";
			if ((prt[j][i])<10) cout<<" ";
		}
		cout<<endl;
	}
}
	else cout<<"No answer! ";
cout <<endl;
}

};

void main()
{
	cout<<"馬踏棋盤"<<endl<<endl;
	HOUSE hh;
	hh.input();
	hh.findway();
	hh.print();
	cout<<endl<<"蔡杰　計機０２（７）　學號：200209124105"<<endl<<endl;
	cout<<"Press Enter to exit."<<endl;
	getchar();
}