main.cpp

马踏棋盘和平衡树算法的演示,数据结构的课程设计,两个

#include<stdio.h>
#include<iomanip.h>
#include<iostream.h>
#include<stdlib.h>


#define FALSE 0
#define TRUE  1

const int MAX_DIR=8;
const int MAX_WIDTH=30;
const int width=8;//棋盘宽度

//棋盘各种属性类型
typedef struct{
	
	int curr_x,curr_y;//马当前位置
	int step;//马已经游艺机历的步数
	int last_direction;//上一位置到当前位置马所选取的方向
	int var_x[MAX_DIR];
	int var_y[MAX_DIR];//记住一x,y的值的变化
	int chessboard[MAX_WIDTH][MAX_WIDTH];//棋盘数组
	int	direction[MAX_WIDTH][MAX_WIDTH];//记录马在某个位置是从上一位置选择第几个方向到达的
	int total_step;//总步数
	bool cannot[ MAX_WIDTH][ MAX_WIDTH][MAX_DIR];//用来记录某个位置某个方向是否已经成探试过

}knight;

void print(knight &H);//打印马走一步的棋盘位置
bool tourist(int start_x,int start_y,knight &H);//马行棋的路线
void init_direction(knight &H);//初始化马走棋的方向(共8个)
void init_chessboard(knight &H);//初始化棋盘
void set_start(int x,int y,knight &H);//初始化马的初始位置
bool select_direction(knight &H);//选择马行棋的方向
void backward(knight &H);//马后退
void forward(knight &H);//马前进
bool is_legal(int x,int y,knight H);//马行棋的位置是否合法
bool back_to_start(knight H);//马是否回到初始位置
bool is_end(knight H);//马是否走完整个棋盘
bool fastselect_direction(knight &H);//快速选择马行棋方向
void fastbackward(knight &H);//马后退
void fastforward(knight &H);//马前进
void init_cannot(knight &H);//用来记录某个位置某个方向是否已经探试过	

	
void print(knight &H)//打印棋盘
{
	printf("马蹋棋盘(求出从某一起点出发的多条以至全部行走路线)\n");
	printf("\n说明:本程序有两种方法!一种为慢速探索,一种为快速探索!\n");
	 
	int x,y;
	cout<<"+";
	for(x=0;x<width;x++)
		cout<<"----+";
	cout<<endl;
	for(x=0;x<width;x++)
	{
		cout<<"|";
		for(y=0;y<width;y++)
			cout<<setw(2)<<H.chessboard[x][y]<<setw(3)<<"|";
		cout<<endl;
		cout<<"+";
		for(y=0;y<width;y++)
			cout<<"----+";
		cout<<endl;
	}
	cout<<"\n\n当前马游历的总步数"<<H.total_step <<endl;

}


void init_direction(knight &H)//日字走法,共八种方向
{
	H.var_x[0]=-2;  H.var_y[0]=1;
	H.var_x[1]=-1;  H.var_y[1]=2;
	H.var_x[2]=1;   H.var_y[2]=2;
	H.var_x[3]=2;   H.var_y[3]=1;
	H.var_x[4]=2;   H.var_y[4]=-1;
	H.var_x[5]=1;   H.var_y[5]=-2;
	H.var_x[6]=-1;  H.var_y[6]=-2;
	H.var_x[7]=-2;  H.var_y[7]=-1;
}
void init_chessboard(knight &H)//棋盘初始化为0
{
	int x,y;
	for(x=0;x<width;x++)
	{
		for(y=0;y<width;y++)
			H.chessboard[x][y]=0;

	}
}
void set_start(int x,int y,knight &H)//设置初始值
{
	H.curr_x=x;H.curr_y=y;H.step=1;
	H.chessboard[x][y]=H.step;
	H.step=H.step+1;
	H.direction[x][y]=MAX_DIR;
	H.last_direction=MAX_DIR;
}
bool select_direction(knight &H)
{
	int try_x,try_y;
	if(H.last_direction==MAX_DIR)//该位置是否为新位置
		H.last_direction=0;//从第0个方向开始
	else
		H.last_direction+=1;//从下一个方向开始
	while(H.last_direction<MAX_DIR)
	{
		try_x=H.curr_x+H.var_x[H.last_direction];
		try_y=H.curr_y+H.var_y[H.last_direction];//探试下一位置
		if(is_legal(try_x,try_y,H))break;
		H.last_direction=H.last_direction+1;
	}
	if(H.last_direction==MAX_DIR)
		return FALSE;//无棋可走
	else 
		return TRUE;
}
void backward(knight &H)
{
	H.step=H.step-1;
	H.chessboard[H.curr_x][H.curr_y]=0;//返回原来值
	H.last_direction=H.direction[H.curr_x][H.curr_y];//取上一位置到当前位置所选区取的方向
	H.curr_x=H.curr_x-H.var_x[H.last_direction];
	H.curr_y=H.curr_y-H.var_y[H.last_direction];//返回上一位置

}
void forward(knight &H)
{
	H.curr_x=H.curr_x+H.var_x[H.last_direction];
	H.curr_y=H.curr_y+H.var_y[H.last_direction];
	H.chessboard[H.curr_x][H.curr_y]=H.step;
	H.step++;
	H.direction[H.curr_x][H.curr_y]=H.last_direction;//保存上一位置到当前位置所选取的方向
	H.last_direction=MAX_DIR;//表示该位置为新位置
}
bool is_legal(int x,int y,knight H)
{
	if(x<0||x>=width) return FALSE;
	if(y<0||y>=width) return FALSE;//是否超出棋盘
	if(H.chessboard[x][y]>0) return FALSE;//是否已经游历过该位置
	return TRUE;
}
bool back_to_start(knight H)
{
	if(H.step==1)return TRUE;
	else return FALSE;
}
bool is_end(knight H)
{
	if(H.step>width*width)return TRUE;
	else return FALSE;
}
bool tourist(int start_x,int start_y,knight &H)
{
	init_chessboard(H);
	set_start(start_x,start_y,H);
	do
	{
		if(select_direction(H)){forward(H);H.total_step ++;print(H);system("cls");}
		else {backward(H);H.total_step ++;}
	}while(!back_to_start(H)&&!is_end(H));
	if(back_to_start(H))
		return FALSE;//没有解决方案
	else
		return TRUE;
}


bool fasttourist(int start_x,int start_y,knight &H)
{
	init_chessboard(H);
	set_start(start_x,start_y,H);
	do
	{
		if(fastselect_direction(H)){fastforward(H);H.total_step ++;print(H);_sleep(80);system("cls");}
		else {fastbackward(H);H.total_step ++;_sleep(200);system("cls");}
	}while(!back_to_start(H)&&!is_end(H));
	if(back_to_start(H))
		return FALSE;//没有解决方案
	else
		return TRUE;
}




void init_cannot(knight &H)
{
	int x,y,dir;
	for(x=0;x<width;x++)
		for(y=0;y<width;y++)
			for(dir=0;dir<width;dir++)
				H.cannot[x][y][dir]=FALSE;
}

bool fastselect_direction(knight &H)
{
	int try_x,try_y,next_x,next_y;
	int dir_index,next_index;
	int min_dir,count;
	min_dir=MAX_DIR;
	H.last_direction=MAX_DIR;
	for(dir_index=0;dir_index<MAX_DIR;dir_index++)
	{//选择一个方向使得根据该方向推进到下一位置时,在该位置可选的方向最少
		try_x=H.curr_x+H.var_x[dir_index];
		try_y=H.curr_y+H.var_y[dir_index];
		if(is_legal(try_x,try_y,H)&&!H.cannot[H.curr_x][H.curr_y][dir_index])
		{//这个位置作为下一个位置是合法的,计算该位置的可选方向
			count=0;
			for(next_index=0;next_index<MAX_DIR;next_index++)
			{//记录具有最少可选方向的下一位置
				next_x=try_x+H.var_x[next_index];
				next_y=try_y+H.var_y[next_index];
				if(is_legal(next_x,next_y,H)) count++;
			}
			if(count<min_dir)
			{//记录具有最不可选方向的下一位置
				H.last_direction=dir_index;
				min_dir=count;
			}
		}
	}
	if(H.last_direction==MAX_DIR)
		return FALSE;
	else 
		return TRUE;
	

}
void fastbackward(knight &H)
{
	int dir;
	H.step=H.step-1;
	H.chessboard[H.curr_x][H.curr_y]=0;

	for(dir=0;dir<MAX_DIR;dir++)
		H.cannot[H.curr_x][H.curr_y][dir]=FALSE;
	H.last_direction=H.direction[H.curr_x][H.curr_y];
	H.curr_x=H.curr_x-H.var_x[H.last_direction];
	H.curr_y=H.curr_y-H.var_y[H.last_direction];


}
void fastforward(knight &H)
{
	H.cannot[H.curr_x][H.curr_y][H.last_direction]=TRUE;
	H.curr_x=H.curr_x+H.var_x[H.last_direction];
	H.curr_y=H.curr_y+H.var_y[H.last_direction];
	H.chessboard[H.curr_x][H.curr_y]=H.step;
	H.step++;
	H.direction[H.curr_x][H.curr_y]=H.last_direction;
	H.last_direction=MAX_DIR;
	
}

void main()
{

  	knight H;
	int i;
	H.total_step =1;
	init_direction(H);
	init_cannot(H);
	int start_x,start_y;
	printf("\n       *********************************************************** \n");
	printf("           马蹋棋盘(求出从某一起点出发的多条以至全部行走路线)        \n");
	printf("\n         制作人:陈平锋 学号:2003040140204 计算机科学与技术(02)班 \n");
	printf("\n       ***********************************************************  \n");
	printf("\n说明:本程序有两种方法!一种为慢速探索,一种为快速探索!\n");
	printf("\n请输入马的初始位置!(0=<x,y<=7)\n");
	printf("start_x=");
	scanf("%d",&start_x);
	printf("start_y=");
	scanf("%d",&start_y);
	system("pause");
	printf("请选择探索方法:");
	printf("\t\t1.慢速探索(即有回溯的过程)\n");
	printf("\t\t\t2.快速探索(几乎没有回溯)\n");
	printf("choice=");
	scanf("%d",&i);
	switch(i)
	{
	case 1:
	
	if(tourist(start_x,start_y,H))
		print(H);
	else
	{
	
		cout<<"\n没解决方案!";
		cout<<"start:("<<start_x<<","<<start_y<<")";
		cout<<"width:"<<width<<endl;
	}
	break;
	case 2:
		
	if(fasttourist(start_x,start_y,H))
		print(H);
	else
	{
		cout<<"\n没解决方案!";
		cout<<"start:("<<start_x<<","<<start_y<<")";
		cout<<"width:"<<width<<endl;
	}
	break;
	}
	system("pause");

}