horse.cpp

里面用两种方法实现了骑士巡游问题

#include <iostream.h> 
#include <stdio.h> 
int map[9][9];//用来标记的二维数组 
int n=5;//实际计算时的棋盘大小，超过5时运算时间过长，小于5时无解 
int diry[]={ 2, 1, -1, -2, -2, -1, 1, 2 };
int dirx[]={ 1, 2, 2, 1, -1, -2, -2, -1 };
int firstx,firsty;
int jie=0;
bool judge(int y,int x)
{ 
	if(x>=0 && x<=n && y>=0 && y<=n && map[y][x]==0) 
		return true; 
	else 
		return false; 
} 
bool check(int y,int x)
{
	if((y-firsty)*(y-firsty)+(x-firstx)*(x-firstx)==5)
		return true;
	return false;
}
void set(int y,int x,int t)
{ 
	if(t==(n+1)*(n+1)&&check(y,x))
	{ 
		map[y][x]=t;
		jie=1;
		cout<<"一种可能的走法:"<<endl; 
		for(int i=0;i<=n;i++)
		{ 
			for(int j=0;j<=n;j++)
			{ 
				if(map[i][j]<10) 
				cout<<" "; 
				cout<<" "<<map[i][j]; 
			} 
		cout<<endl<<endl; 
		} 
		map[y][x]=0; 
		return; 
	} 
	else
	{
		if(jie==1)
			return;
		if(map[y][x]==0)
		{ 
			map[y][x]=t; 
			int nextt=t+1; 
			for(int i=0;i<8;i++)
			{ 
				if(judge(y+diry[i],x+dirx[i])) 
					set(y+diry[i],x+dirx[i],nextt); 
			} 
		map[y][x]=0; 
		} 
	} 
} 
void main()
{
	for(int i=1;i<=8;i++) 
		for(int j=1;j<=8;j++) 
			map[i][j]=0; 
	cout<<"请输入起始点坐标"<<endl;		
	cin>>firstx>>firsty;
	set(firsty,firstx,1);
}