knight4.c

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

//骑士巡游问题
#include<stdio.h>
#define MAX 20

int n, m, curr_x, curr_y, step, dir;
int val[8][2]={{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1}};
int chess[MAX][MAX], direction[MAX][MAX], last_dir[MAX*MAX];

int main()
{
	int i,j;
	void trave(int x, int y);
	scanf("%d%d",&n,&m);
	while(scanf("%d%d",&curr_x,&curr_y)!=EOF)
	{
		dir=0;
		step=0;
		for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			chess[i][j]=-1;
			direction[i][j]=0;
		}
		trave(curr_x, curr_y);
		
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
			printf("%d ",chess[i][j]);
			printf("\n");
		}
	}
	return 0;
}

void trave(int x, int y)
{
	int i,j;	
	int tx, ty;
	/*for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
			printf("%d ",chess[i][j]);
			printf("\n");
		}
	printf("\n");*/

	while(step<=n*n)
	{
		if(dir>=8)
		{
			chess[x][y]=-1;
			direction[x][y]=0;
			tx=x-val[last_dir[step]][0];
			ty=y-val[last_dir[step]][1];
			dir=direction[tx][ty]+1;
			step--;
			/*if(dir>=8)
			{
				chess[tx][ty]=-1;
				direction[tx][ty]=0;
				step--;
				continue;
			}*/
			trave(tx,ty);
			continue;
		}
		//direction[x][y]=dir;
		tx=x+val[dir][0];
		ty=y+val[dir][1];
		if(tx>=0 && tx<n && ty>=0 && ty<m && chess[tx][ty]<0)
		{
			step++;
			chess[x][y]=step;
			direction[x][y]=dir;
			last_dir[step]=dir;
			dir=0;
			trave(tx, ty);
		}
		else dir++;
	}
}