标题:马踏棋盘回溯的问题~~
只看楼主
ogiso_pest
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2008-6-26
 问题点数:0 回复次数:1 
马踏棋盘回溯的问题~~
马踏棋盘~~
老师不允许使用递归调用!因为这样就太简单了!
使用回溯法!
但是第一次回溯(八个方向都已经走过,不可以再走)后,就终止了!单步调适发现else语句以后的参数i,j没有传进来,但是找不出到底是怎么回事?
请大家帮忙看看~
谢谢了

#include <stdio.h>
#include <malloc.h>
#define   N   8
#define   TRUE   1
#define   FALSE   0

int   HTry1[]={-2,-1,1,2,2,1,-1,-2};
int   HTry2[]={1,2,2,1,-1,-2,-2,-1};
int   map[N][N]={0};     //使用数组map表示8*8的棋盘
int   board[N*N]={0};   //使用数组board表示马每次走的方向
int   count=0;

typedef   struct   Position
{
int   x;
int   y;
struct   Position   *next;
}StackNode,*StackList;

void   InitStack(StackList   *horse)
{
*horse=(StackList)malloc(sizeof(StackNode));
(*horse)-> next=NULL;
}

int   Push(StackList   horse,int   x,int   y)
{
StackNode   *temp;
temp=(StackList)malloc(sizeof(StackNode));
if(temp==NULL)
return   FALSE;
temp-> x=x;
temp-> y=y;
temp-> next=horse-> next;
horse-> next=horse;
return   TRUE;
}

int   Pop(StackList   horse,int   *x,int   *y)
{
StackNode   *temp;
temp=horse-> next;
if(temp==NULL)
return   FALSE;
else
{
*x=temp-> x;
*y=temp-> y;
horse-> next=temp-> next;
free(temp);
return   TRUE;
}
}

int   CanJump(int   i,int   j)
{
if(i> =0&&i <8&&j> =0&&j <8&&map[i][j]==0)
return   TRUE;
return   FALSE;
}   //判断map[i][j]是否可以走

void   HorseTravel(StackList   horse,int   x,int   y)
{
int   i,j,start=0;

Push(horse,x,y);
map[x][y]=count+1;

while(count!=64)
{
i=x;
j=y;

for(start=board[count];start <8;start++)
{
i+=HTry1[start];
j+=HTry2[start];
if(CanJump(i,j))
break;
i-=HTry1[start];
j-=HTry2[start];
}   //   依照次序,八个方向挨个试探是否可以走

if(start <8)     //此时8个方向重有一个可以走
{
board[count]=start;     //将马选择走的方向保存在数组board中
map[i][j]=++count+1;   //将马选择走到的点的map改为走的顺序
printf( "%d   %d   \n ",i,j);   //方便查看,打印走的点的坐标
                                                        Push(horse,i,j);   //将马选择走到的点压栈
x=i;
y=j;
}
else   //此时8个方向都无法走
{
map[i][j]=0;   //将当前无法继续走的点的map设置为0,表示没有走过,以后可以选择走
Pop(horse,&i,&j);     //将当前的马的位置出栈
i=horse-> x;     //   让i为无法继续走的位置的前一个位置的x
j=horse-> y;     //让j为无法继续走的位置的前一个位置的y
board[count]++;   //让反悔走的点的方向加1
}
}
}


void   PrintMap()
{
int   i,j;
for(i=0;i <N;i++)
{
for(j=0;i <N;i++)
printf( "%d   ",map[i][j]);
printf( "\n ");
}
}

int   main()
{
int   x,y;
StackList   horse;

InitStack(&horse);
printf( "请输入起始位置(0-7): ");
scanf( "%d%d ",&x,&y);

HorseTravel(horse,x,y);
PrintMap();

getch();
return   0;
}
搜索更多相关主题的帖子: 棋盘 回溯 
2008-10-12 15:09
multiple1902
Rank: 8Rank: 8
等 级:贵宾
威 望:42
帖 子:4881
专家分:671
注 册:2007-2-9
得分:0 
不给递归调用那你可以考虑手工维护系统栈
2008-10-12 18:39



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-237791-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.285742 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved