#include<iostream>
#include<algorithm>
#include<graphics.h>
#include<conio.h>
#define dtx 95 //棋盘一格的宽度
#define originx 45 //左上角第一个点坐标
#define originy 20
#define boardx 9
#define boardy 10
#define maxx 9999
using namespace std;

class stepk
{
public:
	int nk[8];
};

class chessesboard
{
private:
	int total,origin,cellsize;
	int checks[boardx][boardy];
	
public:
	chessesboard(int ori=0,int cel=0);
	int check(int x,int y);
	void mark(int x,int y);
	void remark(int x,int y);
	int win();
};

class horse
{
private:
	int x,y;
	int dx[8];
	int dy[8];
public:
	horse(int ix=0,int iy=0);
	int step(int k,chessesboard& c);
	void back(int k, chessesboard& c);
	void inityouhua(chessesboard& c);
	int tk(int k);
};

void play(int* x,int* y);
class route
{
public:
	int x[boardx*boardy+1],y[boardx*boardy+1];
	void show()
	{
		cout<<"("<<x[1]<<","<<y[1]<<")";
		for(int i=2;i<=boardx*boardy;i++)
		{
			cout<<"→";
			cout<<"("<<x[i]<<","<<y[i]<<")";
			if(i%10==0) 
				cout<<endl;
		}
		char c;
		cout<<"\n是否进入动态演示 y/n"<<endl;
		cin>>c;
		if(c=='y')
			play(x,y);
			
			
	}
};

int sum; route r;
int youhua[boardx][boardy]={0};
stepk stepks[boardx*boardy];

chessesboard::chessesboard(int ori,int cel)
{
	origin=ori;
	cellsize=cel;
	total=0;
	memset(checks,0,sizeof(int)*(boardx)*(boardy));
}

int chessesboard::check(int x,int y)
{
	return checks[x][y];
}

void chessesboard::mark(int x,int y)
{
	checks[x][y]=1;
    total++;
	r.x[total]=x;
	r.y[total]=y;


}

void chessesboard::remark(int x,int y)
{
	checks[x][y]=0;
	total--;
}

int chessesboard::win()
{
	if(total==boardx*boardy)
		return 1;
	else
		return 0;
}

void horse::inityouhua(chessesboard& c)
{
	for(int i=0;i<boardx;i++)
		for(int j=0;j<boardy;j++)
		{
			for (int k=0;k<8;k++)
				if(! (i+dx[k]<0 || i+dx[k]>=boardx || j+dy[k]<0 || j+dy[k]>=boardy))
					youhua[i][j]++;
		}
	int sk[8],t=0,temp,temp1;
	for( i=0;i<boardx;i++)
		for(int j=0;j<boardy;j++)
		{
			for (int k=0;k<8;k++)
				if( i+dx[k]<0 || i+dx[k]>=boardx || j+dy[k]<0 || j+dy[k]>=boardy)
					sk[k]=maxx;
				else
					sk[k]=youhua[i+dx[k]][j+dy[k]];
			for(k=0;k<8;k++)
				stepks[t].nk[k]=k;
			

			for(int i1=0;i1<7;i1++)
			{	
				temp=i1;
				for(int j1=i1+1;j1<8;j1++)
				{	
					if(sk[temp]>sk[j1])
					{
						temp=j1;
					}
				}
				temp1=sk[temp];
				sk[temp]=sk[i1];
				sk[i1]=temp1;
				temp1=stepks[t].nk[i1];
				stepks[t].nk[i1]=stepks[t].nk[temp];
				stepks[t].nk[temp]=temp1;

			}
			t++;
	
		}
			


}

horse::horse(int ix,int iy)
{
	x=ix;
	y=iy;
	int idx[8]={1,1,-1,-1,2,2,-2,-2};
	int idy[8]={2,-2,2,-2,1,-1,1,-1};
	for (int i=0;i<=7;i++)
	{
		dx[i]=idx[i];
		dy[i]=idy[i];
	}
}

int horse::step(int tk,chessesboard& c)
{
	if( x+dx[tk]<0 || x+dx[tk]>=boardx || y+dy[tk]<0 || y+dy[tk]>=boardy || c.check(x+dx[tk],y+dy[tk]) )
		return 0;
	else
	{
		x+=dx[tk];
		y+=dy[tk];
		c.mark(x,y);
		return 1;
	}
		
}

void horse::back(int tk,chessesboard& c)
{
	c.remark(x,y);	
	x-=dx[tk];
	y-=dy[tk];
	
}

int horse::tk(int k)
{
	return stepks[x*boardy+y].nk[k];
}







int abs(int a)
{
	if(a<0)a*=-1;
	return a;
}
//copy img2 to img1
void copy_img(IMAGE* img1,IMAGE* img2)
{
	IMAGE* now_working = GetWorkingImage();
	Resize(img1, img2->getwidth(), img2->getheight());
	SetWorkingImage(img2);
	getimage(img1,0,0,img1->getwidth(),img1->getheight());
	SetWorkingImage(now_working);
}


//【重载】排除颜色avoid_color,容差为deviation
void Blur(IMAGE *pimg,int count,int avoid_color,int deviation)
{
	DWORD*	pMem = GetImageBuffer(pimg);

	COLORREF color;
	//记录排除颜色色彩
	int avoid_r=GetRValue(avoid_color);
	int avoid_g=GetGValue(avoid_color);
	int avoid_b=GetBValue(avoid_color);
	//记录考察点
	int R,G,B;
	int r,g,b;
	int	num		= 0;
	int	width	= pimg->getwidth();
	int	height	= pimg->getheight();


	// 计算 9 格方向系数
	int	cell[9] = {-(width + 1), - width, -(width - 1), -1, 0, 1, width - 1, width, width + 1};

	if(count<1)
	{
		count=1;
	}
	else if(count>50)
	{
		count=50;
	}

	for(;count>0;count--)
	{
		// 逐个像素点读取计算
		for(int i = width * height - 1; i >= 0; i--)
		{
			R = GetRValue(pMem[i]);					
			G = GetGValue(pMem[i]);					
			B = GetBValue(pMem[i]);
			if( (abs(R-avoid_r) <= deviation) && (abs(G-avoid_g) <= deviation) && (abs(B-avoid_b) <= deviation) )
			{
				continue;
			}
			// 累加周围 9 格颜色值
			for(int n=0, m=0; n < 9; n++)
			{
				// 位置定位
				num = i+cell[n];

				// 判断位置值是否越界
				if(num < 0 || num >= width * height || num==i)
				{
					color = pMem[i];		// 将越界像素赋值为中央点
				}
				else
				{
					R = GetRValue(pMem[num]);					
					G = GetGValue(pMem[num]);					
					B = GetBValue(pMem[num]);
					if( (abs(R-avoid_r) <= deviation) && (abs(G-avoid_g) <= deviation) && (abs(B-avoid_b) <= deviation) )
					{
						color = pMem[i];
					}
					else
					{
						color = pMem[num];
					}
				}
				
				// 累加颜色值
				r += GetRValue(color);					
				g += GetGValue(color);					
				b += GetBValue(color);					
			}
			// 将平均值赋值该像素
			pMem[i] = RGB(r / 9, g / 9, b / 9);
			r = g = b = 0; 
		}
	}
}
//排除颜色avoid_color,容差为deviation；透明度tp(transparency)从0到100；效果effect（1为反相，2为黑白，其他为无）,light亮度加成（1不变）
void my_putimg(int dstX,int dstY,IMAGE *pimg,int avoid_color,int deviation,float light,int tp,int effect)
{
	int x,y,num;
	int R,G,B;//记录贴图某点色彩
	//记录排除颜色色彩
	int avoid_r=GetRValue(avoid_color);
	int avoid_g=GetGValue(avoid_color);
	int avoid_b=GetBValue(avoid_color);
	IMAGE pSrcImg;//背景图 
	IMAGE tempimg;//临时贴图
	copy_img(&tempimg,pimg);
	SetWorkingImage(NULL);//对默认绘图窗口的绘图操作
	getimage(&pSrcImg,dstX,dstY,pimg->getwidth(),pimg->getheight());
	
	//透明度容错
	if(tp<0)
	{
		tp=0;
	}
	else if(tp>100)
	{
		tp=100;
	}
	
	
	// 获取背景指向显存的指针
	DWORD* bk_pMem = GetImageBuffer(&pSrcImg);

	//贴图指向显存的指针
	DWORD* pMem = GetImageBuffer(&tempimg);
	for(y=0;y<pimg->getheight();y++)
	{
		for(x=0;x<pimg->getwidth();x++)
		{
			num = y*pimg->getwidth()+x;
			R=GetRValue(pMem[num]);
			G=GetGValue(pMem[num]);
			B=GetBValue(pMem[num]);
			if( (abs(R-avoid_r) <= deviation) && (abs(G-avoid_g) <= deviation) && (abs(B-avoid_b) <= deviation) )
			{
				pMem[num] = bk_pMem[num];
			}
			else
			{
				if(light>0 && light<1)
				{
					R=int(R*light);
					G=int(G*light);
					B=int(B*light);
				}
				else if(light>1)
				{
					R=min(int(R*light),255);
					G=min(int(G*light),255);
					B=min(int(B*light),255);
				}
				if(effect==1)//反相
				{
					pMem[num]=0xffffff-pMem[num];
					continue;
				}
				else if(effect==2)//黑白
				{
					R=G=B=int(R*0.299+G*0.587+B*0.114);
				}
				pMem[num] = RGB((R*tp+GetRValue(bk_pMem[num])*(100-tp))/100 , (G*tp+GetGValue(bk_pMem[num])*(100-tp))/100 , (B*tp+GetBValue(bk_pMem[num])*(100-tp))/100 );
			}
		}
	}
	putimage(dstX, dstY, &tempimg);
}


void find(horse& h,chessesboard& c,int k)
{
	int tk;
	if(c.win())
	{
		sum++;
		r.show();
		h.back(k,c);
		exit(0);
	}

	for(int i=0;i<=7;i++)
	{
		tk=h.tk(i);
		if(h.step(tk,c))
			find(h,c,tk);
	}
	h.back(k,c);
	return;

}

void play(int* x,int* y)
{
	initgraph(922,966);
	IMAGE board_img,horse_img,step_img;
	loadimage(&board_img,"board.jpg");
	loadimage(&horse_img,"horse.jpg");
	loadimage(&step_img,"step.jpg");
	putimage(0,0,&board_img);

	char s[5],s1[100]=_T("PS:按下任一字母键，马往前挑一步。(注意切换英文键盘)");

	setbkmode(TRANSPARENT);
	
	settextstyle(20, 0, _T("黑体"));
	settextcolor(0x000000);
	outtextxy(120,450, s1);

	settextstyle(40, 0, _T("宋体"));
	settextcolor(0xffffff);
	for(int i=1;i<=boardx*boardy;i++)
	{
		if(i>=2 && i<10)
		{
			my_putimg(originx+(x[i-1]*dtx),originy+(y[i-1]*dtx),&step_img,0x000000,50,1,100,3);
			sprintf(s, "%d", i-1);
			outtextxy(originx+25+(x[i-1]*dtx),originy+18+(y[i-1]*dtx), s);
		}
		else if(i>=10)
		{
			my_putimg(originx+(x[i-1]*dtx),originy+(y[i-1]*dtx),&step_img,0x000000,50,1,100,3);
			sprintf(s, "%d", i-1);
			outtextxy(originx+18+(x[i-1]*dtx),originy+18+(y[i-1]*dtx), s);
		
		}
			

		my_putimg(originx+(x[i]*dtx),originy+(y[i]*dtx),&horse_img,0xFFFFFF,40,1,100,3);
		getch();

	}
	sprintf(s, "%d", i-1);
	my_putimg(originx+(x[i-1]*dtx),originy+(y[i-1]*dtx),&step_img,0x000000,50,1,100,3);
	outtextxy(originx+17+(x[i-1]*dtx),originy+18+(y[i-1]*dtx), s);
	getch();
	closegraph();
}



int main()
{
	chessesboard c; int x,y;

	cout<<"input x y(马的初始位置，注意坐标从0开始)"<<endl;
	cin>>x>>y;

	horse h(x,y);
	h.inityouhua(c);


	sum=0;
	c.mark(x,y);
	find(h,c,0);

	return 0;
}