/*
優點：時間復雜度比較小，花費時間少。空間復雜度相對增加
缺點：棋盤大小固定不變；全局變量多，功能函數可移植性差些
其他：代碼中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個文件信息