horse_head.cpp

马踏棋盘的程序设计 设计一个国际象棋的马踏遍棋盘的演示程序。 将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中

#include "horse_head.h"
#include "assert.h"

// the implement of all funcions
void	Init_Stack(stack_step& steps)
{
	steps.pBase=steps.pTop=(step*)malloc(sizeof(stack_step)*STACK_TOTAL);
	steps.total_size=STACK_TOTAL;
};

bool	IsEmpty(stack_step steps)
{
	if(steps.pBase==steps.pTop)
		return true;
	return false;
};

bool	Push(stack_step& steps, step s)
{
	if(steps.pTop-steps.pBase==steps.total_size)
	{
		steps.pBase=(step*)realloc(steps.pBase,steps.total_size+STACK_INCREMENT);
		if(!steps.pBase)
			return false;
		steps.pTop=steps.pBase+steps.total_size;
		steps.total_size+=STACK_INCREMENT;
	}

	//memcpy(steps.pTop,(void*)&s,sizeof(step));
	steps.pTop->direction=s.direction;
	steps.pTop->x=s.x;
	steps.pTop->y=s.y;
	(steps.pTop)++;
	return true;
};

bool	Popup(stack_step& steps, step& s)
{
	if(IsEmpty(steps))
		return false;
//	memcpy(&s,steps.pTop,sizeof(step));
	(steps.pTop)--;
	s.direction=steps.pTop->direction;
	s.x=steps.pTop->x;
	s.y=steps.pTop->y;
	return true;
};

void	GetTop(stack_step& steps,step& s)
{
	if(IsEmpty(steps))
		exit(-1);
//	memcpy(&s,steps.pTop,sizeof(step));
	step* p=steps.pTop-1;
	s.direction=p->direction;
	s.x=p->x;
	s.y=p->y;
}

void	Destroy(stack_step&	steps){
	if(steps.pBase==NULL)
		return ;
	free(steps.pBase);
	steps.pBase=steps.pTop=NULL;
	steps.total_size=0;
};

void	Get_Position(int& x,int& y)
{
	printf("----------------------------------------------------------\n");
	printf("input the initial position of horse in format x  and  y:\n");
	scanf("%d%d",&x,&y);
	printf("Now	let's start....................................\n");
};

void	Show(stack_step& steps,int y/*the order in steps is right*/)
{
		int xpos=0,ypos=y,count=1;
		SetPos(xpos,ypos);
		ypos++;
		printf("the horse step are showed below:");
		frame(xpos,ypos,17,17);
		xpos++;
		ypos++;
		step	cur;
		while(!IsEmpty(steps))
		{
			Popup(steps,cur);
			SetPos(cur.x*4+xpos*2,cur.y*2+ypos);
			printf("%02d",count);
			count++;
			::Sleep(1000);
		}
		SetPos(xpos,ypos+18);
}

void SetPos(int nX, int nY) 

{ 
    HANDLE   hCon;//定义一个句柄 
    hCon = GetStdHandle(STD_OUTPUT_HANDLE);   //获得输出设备的句柄 
    COORD   setps; //定义结构体变量 
    setps.X = nX;    
    setps.Y = nY;  
	CONSOLE_SCREEN_BUFFER_INFO lpConsoleScreenBufferInfo;
	if(nX==-1)
	{
		GetConsoleScreenBufferInfo(hCon,&lpConsoleScreenBufferInfo); 
        setps.X=lpConsoleScreenBufferInfo.dwCursorPosition.X;
	};
	if(nY==-1)
	{
		GetConsoleScreenBufferInfo(hCon,&lpConsoleScreenBufferInfo); 
        setps.Y=lpConsoleScreenBufferInfo.dwCursorPosition.Y;
	}
	SetConsoleCursorPosition(hCon,setps);  //定位
} 
void frame(int x, int y, int width, int height) 

{ 
    for(int nI = 0; nI < height; nI++)  //行数 
    { 
        for(int nJ = 0; nJ < width*2; nJ += 2) //列数，width*2中文符号占两位 
        { 
            SetPos(x + nJ, y + nI); //调用我们前面的函数进行光标的定位 
            if(nI == 0 || nJ == width*2 - 2 || nJ == 0 || nI == height - 1) //只打印四个边 
            { 
                if(nI == 0 && nJ == 0 ) //左上的拐角 
                { 
                    printf("┏"); 
                } 
                else if(nI == 0 && nJ == width * 2 - 2) 
                { 
                        printf("┓");//右上的拐角 
                } 
                else if(nI == height - 1 && nJ == 0) 
                { 
                    printf("┗");//左下的拐角 
                } 
                else if(nI == height - 1 && nJ == width*2 - 2) 
                { 
                    printf("┛");//右下的拐角 
                } 
                else if(nI == 0 || nI == height - 1) 
                { 
                    printf("━");    
                } 
                else 
                { 
                    printf("┃"); 
                } 
            } 
        } 
        printf("\n"); 
    } 
} 

bool	Can_Move(chessboard	cb,int x,int y,int dir)
{
	switch(dir)
	{
	case	LEFT_UP:
		if(y-2<0||x-1<0)
			return false;
		if(cb[y-2][x-1]!=0)
			return false;
		return true;
	case	UP_LEFT:
		if(y-1<0||x-2<0)
			return false;
		if(cb[y-1][x-2]!=0)
			return false;
		return true;
	case	DOWN_LEFT:
		if((y+1>CHESSBOARD-1)||x-2<0)
			return false;
		if(cb[y+1][x-2]!=0)
			return false;
		return true;
	case	LEFT_DOWN:
		if((y+2>CHESSBOARD-1)||x-1<0)
			return false;
		if(cb[y+2][x-1]!=0)
			return false;
		return true;
	case	RIGHT_DOWN:
		if((y+2>CHESSBOARD-1)||x+1>CHESSBOARD-1)
			return false;
		if(cb[y+2][x+1]!=0)
			return false;
		return true;
	case	DOWN_RIGHT:
		if((y+1>CHESSBOARD-1)||x+2>CHESSBOARD-1)
			return false;
		if(cb[y+1][x+2]!=0)
			return false;
		return true;
	case	UP_RIGHT:
		if((y-1<0)||x+2>CHESSBOARD-1)
			return false;
		if(cb[y-1][x+2]!=0)
			return false;
		return true;
	case	RIGHT_UP:
		if((y-2<0)||x+1>CHESSBOARD-1)
			return false;
		if(cb[y-2][x+1]!=0)
			return false;
		return true;
	}
	return false;
}

void	Move(int& x,int& y,int dir)
{
	switch(dir)
	{
	case	LEFT_UP:
		y=y-2;
		x=x-1;
		break;
	case	UP_LEFT:
		y=y-1;
		x=x-2;
		break;
	case	DOWN_LEFT:
		y=y+1;
		x=x-2;
		break;
	case	LEFT_DOWN:
		y=y+2;
		x=x-1;
		break;
	case	RIGHT_DOWN:
		y=y+2;
		x=x+1;
		break;
	case	DOWN_RIGHT:
		y=y+1;
		x=x+2;
		break;
	case	UP_RIGHT:
		y=y-1;
		x=x+2;
		break;
	case	RIGHT_UP:
		y=y-2;
		x=x+1;
		break;
	default:
		printf("\nError from Move() that dir is beyond the Metrixs");

	}
}

void	Kernel_Run(chessboard chess,stack_step& steps,int x,int y)
{
	int	count=1;			//记录已经正确填入了多少个空格
	int xpos=x-1,ypos=y-1;		// the current position of horse
	int dir=1;				// the current direction of horse
	int i, j,k=0;				// 循环变量
	long	p=1;
	step	currentstep;	
	assert(IsEmpty(steps));	

	//初始化整个棋盘为0
	for(i=0;i<CHESSBOARD;i++)
		for(j=0;j<CHESSBOARD;j++)
			chess[i][j]=0;

	//主要循环,包含马的走路
	currentstep.direction=1;
	currentstep.x=xpos;
	currentstep.y=ypos;
	Push(steps,currentstep);
	chess[ypos][xpos]=count++;
	while(count<=64)
	{
		GetTop(steps,currentstep);
		dir=currentstep.direction;
		xpos=currentstep.x;
		ypos=currentstep.y;
		//对每个方格的八个方向进行扫描
		for(i=dir;i<=8;i++)
		{
			if(Can_Move(chess,xpos,ypos,i))
			{
				Popup(steps,currentstep);		//用于修改
				currentstep.direction=i+1;		//上一方格的
				Push(steps,currentstep);		//最后访问方向

				Move(xpos,ypos,i);				//移至可访问的下一方格
				break;
			}
		}

		//如果八个方向都是死路，则回到上一个方格中
		if(i==9&&count<=64)
		{
			if(!IsEmpty(steps))
			{
				Popup(steps,currentstep);
				chess[ypos][xpos]=0;
				count--;
			}else
			{
				printf("\n Error from Kernel_Run because stack empty\n");
				return ;
			}
		}else if(count==65)
		{
			chess[ypos][xpos]=count;
			currentstep.x=xpos;
			currentstep.y=ypos;
			currentstep.direction=0;
			break;
		}else  //当扫描有路时把方向又重置为LEFT_UP ,压入栈中
		{
			dir=LEFT_UP;
			currentstep.direction=1;
			currentstep.x=xpos;
			currentstep.y=ypos;
			Push(steps,currentstep);
			chess[ypos][xpos]=count++;
		}
		p++;
		if(p==1000000)
		{
			k++;
			printf(".");
			if(k==15)
			{
				SetPos(0,-1);
				printf("                      ");
				SetPos(0,-1);
				k=0;
			}
			p=1;
		}
	}

}

bool	Converse(stack_step& steps_src,stack_step& steps_dest)
{
	step	temp;
	if(IsEmpty(steps_src)||!IsEmpty(steps_dest))
		return false;
	while(!IsEmpty(steps_src))
	{
		Popup(steps_src,temp);
		Push(steps_dest,temp);
	}
	return true;
}