马踏棋盘
- 格式：doc
- 大小：34.00 KB
- 文档页数：5
#include
#include
#define stack_size 100
#define stackincrement 10
#define N 8
int weight[N][N];
int board[N][N][8];
typedef struct //位置
{
int x;
int y;
}postype;
typedef struct//栈的元素
{
int ord;
postype seat;//点
int di;//马的方向
}elemtype;
typedef struct//定义栈
{
elemtype *base;
elemtype *top;
int stacksize;
}sqstack;
sqstack s;
int initstack()//初始化一个空栈
{
s.base=(elemtype *)malloc(stack_size * sizeof(elemtype));
if(!s.base) return 0;
s.top=s.base;
s.stacksize=stack_size;
return 1;
}
elemtype gettop()//取得栈顶值
{
if(s.top==s.base)
exit(0);
return *(s.top-1);
}
void push(elemtype elem)//将元素压入栈
{
*s.top++=elem;
}
int pop(elemtype *elem)//将栈顶值出栈
{
if(s.top==s.base) return 0;
*elem=*--s.top;
return 1;
}
int stackempty()//判断栈空
{
if(s.top=s.base) return 1;
else return 0;
}
void outputpath()//输出马走过的路径
{
int i,f,k;
sqstack s1=s;
int path[N][N];
for(i=0;s1.top!=s1.base;i++)
{
path[(*s1.base).seat.x][(*s1.base).seat.y]=i+1;
++s1.base;
}
for(f=0;f
printf("\n");
for(k=0;k
printf("\n");
}
int pass(postype curpos)//判断当前位置是否合法
{
sqstack s1=s;
if(curpos.x<0||curpos.x>(N-1)||curpos.y<0||curpos.y>(N-1)) return 0;
for(;s1.top!=s1.base;)
{
--s1.top;
if(curpos.x==(*s1.top).seat.x&&curpos.y==(*s1.top).seat.y) return 0;
}
return 1;
}
postype nextpos(postype curpos,int direction)//8个候选方向
{
switch(direction)
{
case 1:curpos.x+=1;curpos.y-=2; break;
case 2:curpos.x+=2;curpos.y-=1; break;
case 3:curpos.x+=2;curpos.y+=1; break;
case 4:curpos.x+=1;curpos.y+=2; break;
case 5:curpos.x-=1;curpos.y+=2; break;
case 6:curpos.x-=2;curpos.y+=1; break;
case 7:curpos.x-=2;curpos.y-=1; break;
case 8:curpos.x-=1;curpos.y-=2; break;
}
return curpos;//返回新点
}
void setweight()//求各点权值
{
int i,j,k;
postype m;
elemtype elem;
for(i=0;i
for(j=0;j
elem.seat.x=i;
elem.seat.y=j;
weight[i][j]=0;
for(k=0;k<8;k++)
{
m=nextpos(elem.seat,k+1);
if(m.x>=0&&m.x
}
}
}
}
void setmap()//各点的8个方向按权值递增排列
{
int a[8];
int i,j,k,m,min,s,h;
postype n1,n2;
for(i=0;i
for(j=0;j
for(h=0;h<8;h++)//用数组a[8]记录当前位置的下一个位置的可行路径的条数
{
n2.x=i;
n2.y=j;
n1=nextpos(n2,h+1);
if(n1.x>=0&&n1.x
}//对方向索引权值升序排列存入board[N][N][8],不能到达的方向排在最后
for(m=0;m<8;m++)
{
min=9;
for(k=0;k<8;k++)
if(min>a[k])
{
min=a[k];
board[i][j][m]=k;
s=k;
}
a[s]=9;//选过的设为9
}
}
}
}
int horsepath(postype start)
{
postype curpos;
int horsestep=0,off;
elemtype elem;
curpos=start;
do{
if(pass(curpos))//如果当前位置合法
{
horsestep++;
elem.di=0;
elem.ord=horsestep;
elem.seat=curpos;
push(elem);
if(N*N==horsestep) return 1;
off=board[elem.seat.x][elem.seat.y][elem.di]+1;
curpos=nextpos(elem.seat,off);//取得下一个坐标点
}
else{
if(!stackempty())//栈s非空
{
while(!stackempty()&&elem.di==8)
{
pop(&elem);
if(!stackempty())//判断弹出后是否为空
{
elem=gettop();
horsestep=elem.ord;
}
}
if(!stackempty()&&elem.di<8)
{
pop(&elem);
off=board[elem.seat.x][elem.seat.y][++elem.di];
curpos=nextpos(elem.seat,off+1);
push(elem);
}
}
}
}while(!stackempty());
printf("走不通");
return 0;
}
void main()
{
postype start;
initstack();
printf("输入起始位置：（0-7）\nX:");
scanf("%d",&start.x);
printf("Y:");scanf("%d",&start.y);
setweight();
setmap();
horsepath(start);
outputpath();
}
