算法设计与分析----马的周游路线

8 * 8的国际象棋棋盘上的一只马，恰好走过除起点外的其他63个位置各一次，最后回到起点，这条路线称为马的一条Hamilton周游路线。对于给定的m * n的国际象棋棋盘，m和n均为大于5的偶数，且|m-n|≤2，试设计一个分治算法找出马的一条Hamilton周游路线。

下面的代码是实现，并不针对哪一到题，只是简单的实现，也没有用贪心优化。

#include<bits/stdc++.h> 
using namespace std;
struct node
{
	int x,y;
};
node s[100];
int top=-1;
int f[50][50];
int n;
int cnt=1;
int sum=1;
int dis[8][2]={-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1,2,1,1,2};
bool judge(int x,int y)
{
	for(int i=0;i<8;i++)
	{
		if(x+dis[i][0]==0&&y+dis[i][1]==0)
			return true;
	}
	return false;
}
void dfs(int x,int y,int step)
{
	if(step==n*n+1&&judge(x,y))
	{
		f[x][y] = step-1;
		for(int i=0;i<n;i++)
		{
			for(int j =0 ;j<n;j++)
			{
				printf("%5d",f[i][j]);
			}
			printf("\n");
		}
		printf("\n\n\n");
		
		for(int j =0 ;j<=top;j++)
		{
			printf("(%d,%d)\n",s[j].x,s[j].y);
		}
		printf("\n\n\n");
		return ;
	}
	for(int i =0 ;i<8;i++)
	{
		int xx = x+dis[i][0];
		int yy = y+dis[i][1];
		if(xx<0||xx>=n||yy<0||yy>=n||f[xx][yy]!=0)
		{
			continue;
		}
		f[xx][yy] = step;
		node t = {xx,yy};
		s[++top] = t;
		dfs(xx,yy,step+1);
		top--;
		f[xx][yy] = 0;
	}
}
int main()
{
	scanf("%d",&n);
	f[0][0]=1;
	dfs(0,0,2);
}