您所在位置：主题：[讨论]各位老大帮忙看看马踏棋盘为何没结果...3,4班的别COPY
godzii
[专家分：0] 发布于 2007-06-21 21:08:00
#include<malloc.h>
#include<limits.h>
#include<stdio.h>
#include<graphics.h>
#include<io.h>
#include<math.h>
#include<process.h>
#include<conio.h>
#include<dos.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 1
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
#define N 8 /*棋盘大小*/
typedef int Status;
typedef struct chess
{
int x;
int y;
int d;
}chess;
typedef chess SElemType;
int dir[N][N][8]; /*按各点权值递升存放待走方向,每点8个*/
int weight[N][N]; /*各点的权值*/
int board[N][N];
int step[N][N];
int HTry1[8]={-2,-1,1,2,2,1,-1,-2};
int HTry2[8]={1,2,2,1,-1,-2,-2,-1};
char ch;
int h,i,j,k,l,st,x,y;
/*栈的顺序存储表示 */
typedef struct SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */
Status InitStack(SqStack *S)
{ /* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
Status GetTop(SqStack S,SElemType *e)
{ /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
if(S.top>S.base)
{
*e=*(S.top-1);
return OK;
}
else
return ERROR;
}
Status SetTop(SqStack S,SElemType *e)
{
if(S.top>S.base)
{
*(S.top-1)=*e;
return OK;
}
else
return ERROR;
}
Status Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
{
(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;
return OK;
}
/* --------------------------输出行走路线--------------------- */
void output(SqStack S)
{SElemType e;
for(k=1;k<=2*N*N;k++)
{Pop(&S,&e);
i=e.x;j=e.y;
step[i][j]=N*N+1-k;
printf("the answer is:\n");
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{printf("%d ",step[i][j]);}
printf("\n");
}
}
}
/*计算各点的权值,可走的方向越多,权值越小------------------*/
void count()
{
for(i=0;i<N;i++)
for(j=0;j<N;j++)
weight[i][j]=0;
for(k=0;k<N;k++)
{
int x,y;
x=i+HTry1[k];
y=j+HTry2[k];
if(x>=1&&x<=N&&y>=1&&y<=N)
weight[i][j]++;
}
}
int check(int i,int j) /*检查(i,j)是否在棋盘内*/
{
if(i<1||i>8||j<1||j>8)
return 0;
return 1;
}
/*--------------求出各点的最佳方向序列，即优先向权值小的方向
将各点的8个方向按该方向下的目标点的权值递增排列，
不可到达的目标点的方向放在最后面*/
void sort()
{
int m,n1,n2,x1,y1,x2,y2,d1,d2;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
for(k=0;k<8;k++)
dir[i][j][k]=k;
for(k=0;k<8;k++)
{
for(m=k+1;m<8;m++) /*对每个方向考察看有没有更好的*/
{
d1=dir[i][j][k];
x1=i+HTry1[d1];
y1=j+HTry2[d1];
d2=dir[i][j][m];
x2=i+HTry1[d2];
y2=j+HTry2[d2];
n1=check(x1+1,y1+1);
n2=check(x2+1,y2+1);
if((n1==0&&n2)||(n1&&n2&&weight[x1][y1]>weight[x2][y2]))
/*k方向不可达到，而m方向可达到,或都可达到但m方向权值小*/
{
dir[i][j][k]=d2;
dir[i][j][m]=d1; /*交换两个方向值*/
}
}
}
}
}
/*输入函数*/
int scan(int i,int j)
{printf("Please input X :");
scanf("%c",&i);
printf("Please input Y :");
scanf("\n%c",&j);
if(i<'0'||i>'7'||j<'0'||j>'7')
{printf("Input error!\nPlease input again\n");
scan(i,j);}
getch();
}
void main()
{
SqStack a; /*存放路径*/
SqStack b; /*存放方向*/
SElemType c;
SElemType d;/*中间变量*/
SElemType f; /*方向值,x值有效,y值恒为0*/
SElemType m; /*当前点*/
SElemType n; /*下一点*/
InitStack(&a);
InitStack(&b);
printf("Please input X :");
scanf("%c",&x);
printf("Please input Y :");
scanf("\n%c",&y);
st=0;
m.x =x; m.y =y; m.d=0;
board[x][y]=1; /*第一点,在棋盘上标记1,表示已走*/
InitStack(&a); /*建立空栈*/
Push(&a,m); /*起始点的坐标和首选方向入栈*/
while(1)
{
if (st==(N*N-1))/*若已走63步,棋盘上所有格都走完了*/
{ output(a); /*输出路径*/
if(ch=='q') /*q退出*/
break;
else /*回退前一步*/
{ Pop(&a,&m);;/*退栈;*/
Pop(&a,&m);
k=m.d;
m.d=k+1;
Push(&a,m);
st--;
continue;
}
}
if(StackEmpty(a)) break;
GetTop(a,&m);
if(m.d>=8)/*该点所有方向已走完，退栈*/
{x=m.x;y=m.y;
board[x][y]=0;/*抹去痕迹*/
st--;
Pop(&a,&m);/*退栈*/
Pop(&a,&m);
m.d=m.d+1;
Push(&a,m);/*更改方向*/
continue;
}
if(m.d<8)/*方向未走完*/
{x=m.x;y=m.y;
k=m.d;
h=dir[x][y][k];
n.x=x+HTry1[h];
n.y=y+HTry2[h];
if(check(n.x,n.y)&&board[n.x][n.y]==0)
/*目标点在棋盘内且未被走过,则将目标点入栈同时标记当前点为已走过*/
{x=n.x;y=n.y;
board[x][y]=1;
st++; /*记录序号*/
n.d=0;
Push(&a,n); /*存入目标点*/
continue;
}
else/*目标点已被走过或目标点不在棋盘内,换方向*/
{
k=m.d;
Pop(&a,&m);
m.d=k+1;/*取下一个方向*/
Push(&a,m);
continue;/*继续 */
}
}
}
getch();
getch();
}
#include<limits.h>
#include<stdio.h>
#include<graphics.h>
#include<io.h>
#include<math.h>
#include<process.h>
#include<conio.h>
#include<dos.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 1
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
#define N 8 /*棋盘大小*/
typedef int Status;
typedef struct chess
{
int x;
int y;
int d;
}chess;
typedef chess SElemType;
int dir[N][N][8]; /*按各点权值递升存放待走方向,每点8个*/
int weight[N][N]; /*各点的权值*/
int board[N][N];
int step[N][N];
int HTry1[8]={-2,-1,1,2,2,1,-1,-2};
int HTry2[8]={1,2,2,1,-1,-2,-2,-1};
char ch;
int h,i,j,k,l,st,x,y;
/*栈的顺序存储表示 */
typedef struct SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */
Status InitStack(SqStack *S)
{ /* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
Status GetTop(SqStack S,SElemType *e)
{ /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
if(S.top>S.base)
{
*e=*(S.top-1);
return OK;
}
else
return ERROR;
}
Status SetTop(SqStack S,SElemType *e)
{
if(S.top>S.base)
{
*(S.top-1)=*e;
return OK;
}
else
return ERROR;
}
Status Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
{
(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;
return OK;
}
/* --------------------------输出行走路线--------------------- */
void output(SqStack S)
{SElemType e;
for(k=1;k<=2*N*N;k++)
{Pop(&S,&e);
i=e.x;j=e.y;
step[i][j]=N*N+1-k;
printf("the answer is:\n");
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{printf("%d ",step[i][j]);}
printf("\n");
}
}
}
/*计算各点的权值,可走的方向越多,权值越小------------------*/
void count()
{
for(i=0;i<N;i++)
for(j=0;j<N;j++)
weight[i][j]=0;
for(k=0;k<N;k++)
{
int x,y;
x=i+HTry1[k];
y=j+HTry2[k];
if(x>=1&&x<=N&&y>=1&&y<=N)
weight[i][j]++;
}
}
int check(int i,int j) /*检查(i,j)是否在棋盘内*/
{
if(i<1||i>8||j<1||j>8)
return 0;
return 1;
}
/*--------------求出各点的最佳方向序列，即优先向权值小的方向
将各点的8个方向按该方向下的目标点的权值递增排列，
不可到达的目标点的方向放在最后面*/
void sort()
{
int m,n1,n2,x1,y1,x2,y2,d1,d2;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
for(k=0;k<8;k++)
dir[i][j][k]=k;
for(k=0;k<8;k++)
{
for(m=k+1;m<8;m++) /*对每个方向考察看有没有更好的*/
{
d1=dir[i][j][k];
x1=i+HTry1[d1];
y1=j+HTry2[d1];
d2=dir[i][j][m];
x2=i+HTry1[d2];
y2=j+HTry2[d2];
n1=check(x1+1,y1+1);
n2=check(x2+1,y2+1);
if((n1==0&&n2)||(n1&&n2&&weight[x1][y1]>weight[x2][y2]))
/*k方向不可达到，而m方向可达到,或都可达到但m方向权值小*/
{
dir[i][j][k]=d2;
dir[i][j][m]=d1; /*交换两个方向值*/
}
}
}
}
}
/*输入函数*/
int scan(int i,int j)
{printf("Please input X :");
scanf("%c",&i);
printf("Please input Y :");
scanf("\n%c",&j);
if(i<'0'||i>'7'||j<'0'||j>'7')
{printf("Input error!\nPlease input again\n");
scan(i,j);}
getch();
}
void main()
{
SqStack a; /*存放路径*/
SqStack b; /*存放方向*/
SElemType c;
SElemType d;/*中间变量*/
SElemType f; /*方向值,x值有效,y值恒为0*/
SElemType m; /*当前点*/
SElemType n; /*下一点*/
InitStack(&a);
InitStack(&b);
printf("Please input X :");
scanf("%c",&x);
printf("Please input Y :");
scanf("\n%c",&y);
st=0;
m.x =x; m.y =y; m.d=0;
board[x][y]=1; /*第一点,在棋盘上标记1,表示已走*/
InitStack(&a); /*建立空栈*/
Push(&a,m); /*起始点的坐标和首选方向入栈*/
while(1)
{
if (st==(N*N-1))/*若已走63步,棋盘上所有格都走完了*/
{ output(a); /*输出路径*/
if(ch=='q') /*q退出*/
break;
else /*回退前一步*/
{ Pop(&a,&m);;/*退栈;*/
Pop(&a,&m);
k=m.d;
m.d=k+1;
Push(&a,m);
st--;
continue;
}
}
if(StackEmpty(a)) break;
GetTop(a,&m);
if(m.d>=8)/*该点所有方向已走完，退栈*/
{x=m.x;y=m.y;
board[x][y]=0;/*抹去痕迹*/
st--;
Pop(&a,&m);/*退栈*/
Pop(&a,&m);
m.d=m.d+1;
Push(&a,m);/*更改方向*/
continue;
}
if(m.d<8)/*方向未走完*/
{x=m.x;y=m.y;
k=m.d;
h=dir[x][y][k];
n.x=x+HTry1[h];
n.y=y+HTry2[h];
if(check(n.x,n.y)&&board[n.x][n.y]==0)
/*目标点在棋盘内且未被走过,则将目标点入栈同时标记当前点为已走过*/
{x=n.x;y=n.y;
board[x][y]=1;
st++; /*记录序号*/
n.d=0;
Push(&a,n); /*存入目标点*/
continue;
}
else/*目标点已被走过或目标点不在棋盘内,换方向*/
{
k=m.d;
Pop(&a,&m);
m.d=k+1;/*取下一个方向*/
Push(&a,m);
continue;/*继续 */
}
}
}
getch();
getch();
}