kinght7.c

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

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

int n, m;
int val[8][2]={{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1}};
long cin;

int main()
{
	int i, j, step, curr_x, curr_y;
	int chess[MAX][MAX];
    int travel(int x, int y, int chess[MAX][MAX] ,int step);
    
	printf("Input(n,m):");
	scanf("%d%d",&n,&m);
	getchar();
	while(1)
	{
		printf("Input(i,j):");
		scanf("%d%d",&curr_x,&curr_y);
		getchar();

		step=1;
		cin=0;
		
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
			chess[i][j]=-1;
	
		//chess[curr_x][curr_y]=1;
		travel(curr_x, curr_y, chess, step);
		
		printf("%ld\n",cin);
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
			printf("%3d",chess[i][j]);
			printf("\n");
		}
	}
	return 0;
}

int travel(int x, int y, int chess[MAX][MAX], int step)  //递归 
{
	int i, j;
	int tx, ty;
	
	/*printf("%ld\n",cin);
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
			printf("%3d",chess[i][j]);
			printf("\n");
		}
	getchar();*/
	
	cin++;
	//step++;
	chess[x][y]=step;
	
	if(step>=n*m)return 1;
	
	for(i=0;i<8;i++)
	{
		tx=x+val[i][0];
		ty=y+val[i][1];
		if(tx>=0 && tx<n && ty>=0 && ty<m && chess[tx][ty]<0)
		{
			if(travel(tx,ty,chess,step+1))return 1;
		}
	}
	chess[x][y]=-1;
	//step--;
	return 0;
}