kinght6.c

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

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

int n, m;
int val[8][2]={{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1}};
int chess[MAX][MAX];
long cin;
int main()
{
	int i,j, curr_x, curr_y, step;
    int travel(int x, int y, int step);
    void Display();
    
	printf("Input(n,m):");
	scanf("%d%d",&n,&m);
	getchar();
	while(1)
	{
		printf("Input(i,j):");
		scanf("%d%d",&curr_x,&curr_y);
		//getchar();
		if(curr_x<0 || curr_y<0)continue;
		
		step=2;
		cin=0;
		
		chess[curr_x][curr_y]=1;
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
			chess[i][j]=-1;

		travel(curr_x, curr_y, step);
	}
	return 0;
}
void Display()
{
	int i, j;
	printf("%ld\n",cin);
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		printf("%3d",chess[i][j]);
		printf("\n");
	}
	cin=0;
}
	
int travel(int x, int y, int step)  //递归 
{
	int i;
	int tx, ty;
	cin++;
	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)
		{
			chess[tx][ty]=step;
			if(step==n*m)Display();
			else travel(tx,ty,step+1);
		}
	}
	chess[x][y]=-1;
}