knight.cpp

这是自己写的骑士巡游问题的源代码

#include<stdio.h>
#define N 8

typedef struct
{
	int vert;
	int horiz;
}offsets;

offsets move[8];

int maze[N][N];
int count=1;

int in_range(int,int);
void tour(int,int);
void print_ans();

int main()
{
	move[0].vert=2;move[0].horiz=1;
	move[1].vert=1;move[1].horiz=2;
	move[2].vert=-1;move[2].horiz=2;
	move[3].vert=-2;move[3].horiz=1;
	move[4].vert=-2;move[4].horiz=-1;
	move[5].vert=-1;move[5].horiz=-2;
	move[6].vert=1;move[6].horiz=-2;
	move[7].vert=2;move[7].horiz=-1;
	
	for(int i=0;i<N;++i)
		for(int j=0;j<N;++j)
			maze[i][j]=0;

	tour(0,0);
	return 0;
}

int in_range(int x,int y)
{
	return(x>=0 && x<N && y>=0 && y<N);
}
void print_ans()
{
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
			printf("%5d ",maze[i][j]);
		printf("\n");
	}
	printf("\n");
}

void tour(int x,int y)
{
	int direct,next_x,next_y;
	
	direct=0;
	for(direct=0;direct<8;direct++)
	{
		next_x=x+move[direct].vert;
		next_y=y+move[direct].horiz;
		if(in_range(next_x,next_y))
			if(maze[next_x][next_y]==0)
			{

				maze[next_x][next_y]=count;
				if(count==N*N)
					print_ans();
				else
				{
					++count;
					tour(next_x,next_y);
				}
				--count;
				maze[next_x][next_y]=0;					
			}		
	}
}