house.cpp

利用递归写的马踏棋盘的代码！希望能对大家有帮助！

# define STACKINTSIZE 100
# define STACKINRCEMENT 10
# include "stdio.h"
# include "stdlib.h"
# include "malloc.h"
# include "time.h"
typedef struct ElemType//定义结构体
{
	int m,n,o;
}ElemType;

typedef struct Stack//定义一个堆栈结构
{
	ElemType *base;
	ElemType *top;
	int stacksize ;
} ;

int HTry1[8] = {-2,-1,1,2,2,1,-1,-2};//用数组表示八个不同的方向
int HTry2[8] = {1,2,2,1,-1,-2,-2,-1};
int count = 1;//全局变量 表示所走的布数
int B[8][8];// 定义一个二维的数组 表示棋盘
int i,j;//全局变量 表示现在的位置
Stack s;//定义一个堆栈

void inint()//初始化棋盘 初始值为0
{
	int i,j;
	for(i = 0;i < 8;i++)
		for(j = 0;j < 8;j++)
			B[i][j] = 0;
}
void push(int a,int b)//压栈
{
	s.top->m = a;
	s.top->n = b;
	
}

void pop()//弹出栈
{
	s.top--;
	i=s.top->m;
	j=s.top->n;
	
	
}
void print(void)//打印棋盘
{
	int i,j;
	for(i = 0;i < 8;i++)
	{
		for(j = 0;j < 8;j++)
			printf("%4d",B[i][j]);
		printf("\n");
	}
}

void select(int a,int b)//搜索棋盘的位置
{
	int u;
	i=a;j=b;
    u=s.top->o;
	if(u == 7 ) //刚开始就是第七的个 加一后 没有路 可选  回溯
	{
		B[i][j]=0;
		pop();
		count--;
	}
    for( u++; u<8; u++)//由于
	{
		if((i + HTry1[u]) >= 0 && (i + HTry1[u]) <= 7 && (j + HTry2[u]) >= 0 && (j + HTry2[u]) <= 7
			&& B[i + HTry1[u]][j + HTry2[u]] == 0 )
		{
			// if(s.top->o == u) 
			// {
			//     continue;
			// } 
			// if(s.top->o == 1 )
			//  continue;
			s.top->o=u;
			s.top++;
			B[i + HTry1[u]][j + HTry2[u]] = ++count;
			i = i+HTry1[u];
			j = j+HTry2[u];
			
			push(i,j);//符合条件的话，将坐标和选择的方向压栈
			
			break;//结束本次循环 
			// select(i,j);
		} 
		
		
		if(u == 7 && !((i + HTry1[u]) >= 0 && (i + HTry1[u]) <= 7 && (j + HTry2[u]) >= 0 && (j + HTry2[u]) <= 7
			&& B[i + HTry1[u]][j + HTry2[u]] == 0 ))//如果循环到最后了 没有找到 则回溯
		{   
			B[i][j]=0;
			pop();
			count--;
		} 
	} 
	
	//print();
	//printf("\n");
	
	
	
	
	
}

void  main()
{
	inint();
	s.base = (ElemType *)malloc(STACKINTSIZE*sizeof(ElemType));
	s.top = s.base;
	for(i=1; i<=64; i++)
	{
		s.top->o=-1;
		s.top++;
	}
	s.top = s.base;
	srand(time(NULL));  //生成随机数 
	i = rand()%8; 
	j = rand()%8;
	printf("%d  %d\n",i,j);
	B[i][j] = 1;
	s.top->m = i;
	s.top->n = j;
    while (count <= 63)
		select (i,j);
	print();
	return ;
}