贪心算法解决骑士游历问题C语言版

C语言解决骑士游历问题，算法是：贪心算法。全局变量比较多。 稍后会在博客写出思路。标题：骑士游历问题（C语言代码）

/*
优点：时间复杂度比较小，花费时间少。空间复杂度相对增加
缺点：棋盘大小固定不变；全局变量多，功能函数可移植性差些
其他：代码中step自加1和自减1的含义。158-160行为什么step赋
值给chessboard[startx][starty]后，就要自加1。若不自加1，当
骑士回溯到原点（但是还有可以试探的方向），重新选择可移动的
方向时，step会等于1，程序会误判骑士已回溯到原点且无可移动方向。
*/
#include
#include
#define width 8		//棋盘宽度
#define max_dir 8	//可以动的方向数目
int chessboard[width][width]={0};//棋盘方格数组，用于保存骑士走的步数
int dir[width][width];//记录当前所在位置前进的方向，骑士需要回溯时使用。等于width时，表示还未记录
int is_visted[width][width][max_dir]={0};//八个可能移动的方向进行初始化，0表示未被访问过
int cur_xcur_y;//当前坐标
int step;	//已走的步数
int last_dir; //记录上一位置从哪个方向移动到当前位置的，某一方向的下标，骑士回溯时使用。
int ktmove_x[max_dir]={-2-11221-1-2}
	ktmove_y[max_dir]={-1-2-2-11221};/*两个数组用来记住选择某个方向后，推进到下一位置时
											x、y方向的值的变化，当骑士需要回溯时才使用*/
//输出骑士巡游结果
void printpath（）
{
	int xy;
	printf（“ +“）;
	for（x=0;x		printf（“----+“）;
	printf（“\n“）;
	for（x=0;x	{
		printf（“ |“）;
		for（y=0;y			printf（“%3d |“chessboard[x][y]）;
		printf（“\n“）;
		printf（“ +“）;
		for（y=0;y			printf（“----+“）;
		printf（“\n“）;
	}
}

//骑士是否成功到达终点
int is_end_sucess（）
{
	if（step>width*width）
		return 1;
	else
		return 0;
}

//骑士是否回到原点
int is_back_to_start（）
{
	if（step==1）
		return 1;
	else
		return 0;
}

//判断骑士要走的位置是否越界或已被游历
int is_legal（int xint y）
{
	if（x<0||x>=width||y<0||y>=width||chessboard[x][y]!=0）
		return 0;
	else
		return 1;
}

//判断下一步是否有可以移动的方向
int select_dir（）
{
	int try_xtry_ynext_xnext_y;
	int ijcountmin_dir;//min_dir是具有最小路径的方向下标，等于max_dir时，表示没有路径可选择
	min_dir=max_dir;/*min_dir==8表示当前位置的所有方向不可用;min_dir<=7时
					表示当前方向可用，min_dir是数组ktmove_x和ktmove_y的下标*/
	last_dir=max_dir;
	for（i=0;i	{
		try_x=cur_x+ktmove_x[i];
		try_y=cur_y+ktmove_y[i];
		if（is_legal（try_xtry_y）==1&&!is_visted[cur_x][cur_y][i]）//找出可选方向的出口数目
		{
			count=0;
			for（j=0;j			{
				next_x=try_x+ktmove_x[j];
				next_y=try_y+ktmove_y[j];
				if（is_legal（next_xnext_y）&&!is_visted[cur_x][cur_y][j]）
					count++;			//出口可用，count自加1
			}
			if（count			{
				last_dir=i;//将当前i值赋给last_direction，最大可以等于7
				min_dir=count;//将count赋值给min_dir，反之，min_dir大小保持不变
			}
		}
	}
	if（min_dir==max_dir）
		return 0;//没有方向可选，调用回溯函数
	else
		return 1;//有方向可选，调用前进函数
}

//骑士前进
void forward（）
{
	is_visted[cur_x][cur_y][last_dir]=1;//骑士当前位置下标是last_dir的方向已经试探过了
	cur_x+=ktmove_x[last_dir];
	cur_y+=ktmove_y[last_dir];
	chessboard[cur_x][cur_y]=step;//骑士前进成功，赋值棋盘当前位置的步数给骑士所在的棋盘方格
	step++;
	dir[cur_x][cur_y]=last_dir;//记录当前所在位置前进的方向，骑士需要回溯时使用。
	last_dir=max_dir;		//初始化last_direction
}

//骑士回溯
void backward（）
{
	int i;
	step--;
	chessboard[cur_x][cur_y]=0;
	last_dir=dir[cur_x][cur_y];//将last_direction重置为上一位置到（curr_xcurr_y）所选择的方向
	for（i=0;i		is_visted[cur_x][cur_y][i]=0;
	cur_x-=ktmove_x[last_dir];
	cur_y-=ktmove_y[last_dir];
	/* 回溯到上一位置，回溯到上一位置之后，在上一位置再试探时

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      30208  2012-12-13 19:35  Page97-Exercise10\Debug\Page97-Exercise10.exe

     文件     309040  2012-12-13 19:35  Page97-Exercise10\Debug\Page97-Exercise10.ilk

     文件     363520  2012-12-13 19:35  Page97-Exercise10\Debug\Page97-Exercise10.pdb

     文件    1966080  2012-12-13 18:45  Page97-Exercise10\ipch\page97-exercise10-93d8e039\page97-exercise10-eb85689f.ipch

     文件        772  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\cl.command.1.tlog

     文件       1532  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\CL.read.1.tlog

     文件        636  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\CL.write.1.tlog

     文件       1590  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\link.command.1.tlog

     文件       2468  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\link.read.1.tlog

     文件       1060  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\link.write.1.tlog

     文件        660  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\mt.command.1.tlog

     文件        974  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\mt.read.1.tlog

     文件        460  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\mt.write.1.tlog

     文件        381  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\Page97-Exercise10.exe.intermediate.manifest

     文件         92  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\Page97-Exercise10.lastbuildstate

     文件       3220  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\Page97-Exercise10.log

     文件      15783  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\Page97-Exercise10.obj

     文件      27648  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\vc100.idb

     文件      61440  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug\vc100.pdb

     文件       4842  2012-12-13 20:07  Page97-Exercise10\Page97-Exercise10\Page97-Exercise10.c

     文件       3241  2012-12-11 22:28  Page97-Exercise10\Page97-Exercise10\Page97-Exercise10.vcxproj

     文件        953  2012-12-11 22:28  Page97-Exercise10\Page97-Exercise10\Page97-Exercise10.vcxproj.filters

     文件        143  2012-12-11 22:16  Page97-Exercise10\Page97-Exercise10\Page97-Exercise10.vcxproj.user

     文件    2117632  2012-12-13 20:07  Page97-Exercise10\Page97-Exercise10.sdf

     文件        918  2012-12-11 22:16  Page97-Exercise10\Page97-Exercise10.sln

    ..A..H.     15360  2012-12-13 20:07  Page97-Exercise10\Page97-Exercise10.suo

     目录          0  2012-12-13 18:45  Page97-Exercise10\ipch\page97-exercise10-93d8e039

     目录          0  2012-12-13 19:35  Page97-Exercise10\Page97-Exercise10\Debug

     目录          0  2012-12-13 19:35  Page97-Exercise10\Debug

     目录          0  2012-12-13 18:41  Page97-Exercise10\ipch

............此处省略5个文件信息