knight9.c

《数据结构-使用C语言》第三版

//次算法并不能穷举所有可能的行走方案，应为在不同的点，开始搜索的方向可能不同
//及在同一次搜索中，start的值可以不同， 而在此算法中没到达这个要求，因此只能求解部分解 
//此算法不需要用到递归，所以时间效率比较高 , 时间复杂度为 O(n*m) 
#include<stdio.h>
#include<string.h> 
#define MAX 12

int n, m, start;
int chess[MAX][MAX];
//int val[8][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2},};
int val[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};

int main()
{
	int i, j, k, curr_x, curr_y, test, step, x, y;
	int next(int x, int y);
	int count_dir(int x, int y);
	printf("Input(n,m):");
	scanf("%d%d",&n,&m);
	while(scanf("%d%d",&curr_x,&curr_y))
	{
		test=1;
		start=0;
		while(start <= 7)
		{
			for(i=0;i<n;i++)
			for(j=0;j<m;j++)
			chess[i][j]=-1;
			
			x=curr_x-1;
			y=curr_y-1;
			chess[x][y]=1;
			step=2;
			
			while(1)
			{
				if(step > n*m){
					
				printf("\nNumber:%d\n",test++);
				for(i=0;i<n;i++)
				{
					for(j=0;j<m;j++)
					printf("%4d",chess[i][j]);
					printf("\n");
				}
				start++;
				break;}
				
				k=count_dir(x, y);
				if(k==0)//判断从(x,y)出发无方向可走 
				{
					start++;
					break;
				}
				k=next(x,y);//判断应该从那个方向可走 
				
				x+=val[k][0];
				y+=val[k][1];
				chess[x][y]=step++;
			}
		}
	}
	return 0;
}

int count_dir(int x, int y)
{//统计下一步可走方向的个数
	int i, k;
	int tx,ty, num=0;
	for(i=0;i<8;i++)
	{
		k=(start+i)%8;
		tx=x+val[k][0];
		ty=y+val[k][1];
		if(tx>=0 && tx<n && ty>=0 && ty<m && chess[tx][ty]<0)
		num++;
	}
	return num;
}

int next(int x, int y)
{//放回下一步应该走的方向
	int i, k, dir;
	int tx, ty; 
	int min_dir=10, num;
	
	for(i=0;i<8;i++)
	{
		k=(start+i)%8;
		tx=x+val[k][0];
		ty=y+val[k][1];
		if(tx>=0 && tx<n && ty>=0 && ty<m && chess[tx][ty]<0)
		num=count_dir(tx,ty);
		if(num < min_dir)
		{
			min_dir=num;
			dir=k;
		}
	}
	return dir;
}