zyqishi.cpp

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

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

#define  n 21 //实际计算时的棋盘大小
typedef struct
{
	int dir;
	int score;
} NaviNode;

typedef struct
{
	int x;
	int y;
	int index;
	NaviNode nodes[8];
} point;
point node[(n+1)*(n+1)];
int map[9][9];//用来标记的二维数组 
int step=0;//步骤
int jie=0;
int diry[]={ 2, 1, -1, -2, -2, -1, 1, 2 };
int dirx[]={ 1, 2, 2, 1, -1, -2, -2, -1 };
//没有出边界并且没有被访问过
bool judge(int y,int x)
{
	if(x>=0 && x<=n && y>=0 && y<=n && map[y][x]==-1) 
		return true; 
	else 
		return false; 
} 
//将下一个节点按出度升序排序
void navigator(int t)
{
	int nexty,nextx;
	int tempy,tempx;
	for(int i=0;i<8;i++)
	{
		nexty=node[t].y+diry[i];
		nextx=node[t].x+dirx[i];
		node[t].nodes[i].dir=i;//代表此时的方向
		node[t].nodes[i].score=0;
		int loc=map[nexty][nextx];
		if(judge(nexty,nextx))
		{
			//node[t].index++;
			//计算有多少种走步可能
			for(int j=0;j<8;j++)
			{
				tempx=nextx+dirx[j];
				tempy=nexty+diry[j];
				if(judge(tempy,tempx))
					node[t].nodes[i].score++;
			}
		}
		else
		{
			node[t].nodes[i].score=8888;
		}
	}
	//排序
	int minpos,tmp;
	for(i=0;i<7;i++)
	{
		minpos=i;
		for(int j=i+1;j<8;j++)
		{
			if(node[t].nodes[j].score<node[t].nodes[minpos].score)
				minpos=j;
		}
		tmp=node[t].nodes[i].score;
		node[t].nodes[i].score=node[t].nodes[minpos].score;
		node[t].nodes[minpos].score=tmp;

		tmp=node[t].nodes[i].dir;
		node[t].nodes[i].dir=node[t].nodes[minpos].dir;
		node[t].nodes[minpos].dir=tmp;
	}
	for(i=0;i<8;i++)
		int bian=node[t].nodes[i].score;

}
//检查是否能够成回路
bool check()
{
	if((node[step].x-node[0].x)*(node[step].x-node[0].x)+(node[step].y-node[0].y)*(node[step].y-node[0].y)==5)
		return true;
	return false;
}
void output()
{
	int i,j;
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			if(map[i][j]<10)
				cout<<" ";
			cout<<" "<<map[i][j];
		}
		cout<<endl<<endl;
	}
}
//非递归式查找下一节点
void norecursionsearch()
{
	int nextx,nexty;
	while(step>=0)
	{
		if(node[step].index==8||node[step].nodes[node[step].index].score==8888)
		{
			map[node[step].y][node[step].x] = -1;
			--step;
			continue;
		}
		nextx = node[step].x + dirx[node[step].nodes[node[step].index].dir];
		nexty = node[step].y + diry[node[step].nodes[node[step].index].dir];
	    node[step].index++;

		map[nexty][nextx] = ++step + 1; 
		node[step].x = nextx;
		node[step].y = nexty;
		node[step].index = 0;
		navigator(step);

		if(step==((n+1)*(n+1)-1)&&check())
		{
			cout<<"一种可能的路线"<<endl;
			output();
			return;
		}
	}
}
void main()
{ 
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
			map[i][j]=-1;
	}

    cout<<"请输入起始点坐标"<<endl;		
	cin>>node[step].x>>node[step].y;
	
	node[step].index=0;
	map[node[step].y][node[step].x]=1;
	navigator(step);
	norecursionsearch();
	
}