kinght8.c

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

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

int n, m;
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}};
long cin;

int main()
{
	int i, j, step, curr_x, curr_y, t;
    int travel(int x, int y, 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;
		t=travel(curr_x-1, curr_y-1, step);
		if(t==0)
		{
			printf("NO\n");
			continue;
		}
		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 step)  //递归 
{
	int i, j;
	int tx, ty;
	cin++;
	if(cin>=10000000)return 0;
	
	chess[x][y]=step;
	//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,step+1)==1)return 1;
		}
	}
	chess[x][y]=-1;
	//step--;
	return 0;
}