horseridingboard.txt

用数组来解决关于国际象棋马踏棋盘问题 已经调试无错误

/*----------------姓名：石壮-------------------*/
/*--------------班级：11010601----------------*/
/*----------------学号:062551----------------*/

#pragma once
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INIT_SIZE	8
#define	STACKINCREMENT 57
typedef struct 
{
	int x,y;
}point;
typedef point SElemType;
typedef int Status;
typedef struct  
{
	SElemType *  base;
	SElemType *  top;
	int stacksize;
}SqStack;
Status InitStack(SqStack &s);
Status Push(SqStack &s,SElemType e);
Status Pop(SqStack &s,SElemType &e);
//SqStack..cpp

#include <stdio.h>
#include <malloc.h>

Status InitStack(SqStack &s)
{
	s.base = ( SElemType * )malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!s.base) return OVERFLOW;
	s.top = s.base;
	s.stacksize = STACK_INIT_SIZE;
	return OK;
}
Status Push(SqStack &s,SElemType e)
{
	if (s.top-s.base>=s.stacksize)
	{
		s.base=(SElemType * )realloc(s.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType));
		if (!s.base)
		{
			return OVERFLOW;
		}
		s.top = s.base + s.stacksize;
		s.stacksize+=STACKINCREMENT;
	}
	*s.top++ = e;
	return OK;
}
Status Pop(SqStack &s,SElemType &e)
{
	if(s.top==s.base)
		return ERROR;
	e = *--s.top;
		return OK;
}
//horse.cpp
#include <stdio.h>
#include <malloc.h>


int horizontal[]={2,1,-1,-2,-2,-1,1,2};
int vertical[]={-1,-2,-2,-1,1,2,2,1};
int board[8][8]={0};
int step=1;
SqStack s[65];
SqStack s1;

#define n 8

void exit(point p);//计算出下一步可能位置，按其各个位置下一个位置的和压栈到s[]中
int number(point p);//找出当前位置下一步的各种可能位置,计算可能之和
void next(point p);//找出各个位置并将其步数记录
bool legal(point p);//判断是否可行

void main()
{
	point p;
	printf("输入x(0-%d),y(0-%d)\n",n-1,n-1);
	scanf("%d%d",&p.x,&p.y);
	while(!((p.x>=0)&&(p.x<n)&&(p.y<n)&&(p.y>=0)))
	{
		printf("输入不合法,重输入!\n");
		printf("输入x(0-%d!),y(0-%d!)\n",n-1,n-1);
		scanf("%d%d",&p.x,&p.y);
	}
	
	InitStack(s1);//初始化栈
	next(p);
	for (int i=0;i<n;i++)//打印棋盘
	{
		for (int j=0;j<n;j++)
		{
			printf("%5d",board[i][j]);
		}
		printf("\n");
	}
}
int   number(point p)//找出当前位置下一步的各种可能位置,计算可能之和
{
	point p1;
	int j=0;
for(int i=0;i<8;i++)
	{
		p1.x=p.x+horizontal[i];
		p1.y=p.y+vertical[i];
		if(legal(p1))
		{
			j++;
		}
	}
	return (j);
}
void next(point p)//找出各个位置并将其步数记录
{
		point p1,p2;
		InitStack(s[step]);
		board[p.x][p.y]=step;
		Push(s1,p);
		if(step<n*n)
		{
			exit(p);
			Pop(s[step],p2);
			if ((s[step].base==s[step].top&&number(p2)==0)&&step!=n*n-1)
			{
				Pop(s1,p1);
				board[p1.x][p1.y]=0;	

				--step;
				
				while (s[step].base==s[step].top)
				{
					Pop(s1,p1);
					board[p1.x][p1.y]=0;
					step--;

				}

 				Pop(s[step],p2);
				step++;
				next(p2);
			}//退栈，悔棋
		
			else if(number(p2)==0&&s[step].base!=s[step].top)
			{	
				Pop(s[step],p2);
				step++;
				next(p2);
			}
			else if (number(p2)!=0&&s[step].base==s[step].top)
			{
				step++;
				next(p2);
			}
else 
			{
				step++;
				next(p2);
			}
		}

}
void exit(point p)//计算出下一步可能位置，按其各个位置下一个位置的和压栈到s[]中
{

	point temp;
 	point p1;
 	int j=0;
 	point ap[8]={0};
 	for(int i=0;i<8;i++)
 	{
 		p1.x=p.x+horizontal[i];
 		p1.y=p.y+vertical[i];
 		if(legal(p1))
 		{
			ap[j]=p1;
 			j++;
		}
	}//将下一步的可能位置储存在ap[]中
	for(int count=0;count<number(p)-1;count++)   //使用冒泡法，对下一步的八个规则的从大到小排序 
    {
		for(int k=0;k<number(p)-1;k++)
		{
			if (number(ap[k])<number(ap[k+1]))
			{
				temp=ap[k+1];
				ap[k+1]=ap[k];
				ap[k]=temp;
			}
		}
      }
for (int t=0;t<number(p);t++)	
	{
		Push(s[step],ap[t]);
	}//将可能位置压栈到s[step]
}

bool legal(point p)//判断是否可行
{
	if((p.x>=0)&&(p.x<n)&&(p.y<n)&&(p.y>=0)&&(board[p.x][p.y]==0))
		return true;
	else
		return false;
}