当前位置: 代码迷 >> C语言 >> 马踏棋盘
  详细解决方案

马踏棋盘

热度:439   发布时间:2005-06-22 01:41:00.0
首先选择一个一个点a 再将该点周围的8 个点(按行走规则)入栈 再依次出栈 找到合适的点(在棋盘上 且没有走过)作为下一个行走点b  依此进行再将b周围的八个点入栈  

这样可不可以  是不是有些疏漏  我运行结果 不对 就是找不出

楼上的qq可不可以留下  有机会聊 聊  
----------------解决方案--------------------------------------------------------
其实我没真正做过,但思想大致就这样。
你说的会有疏漏,不知道你是怎么理解,或者你可以举出一个疏漏的例子来……
我上面漏提了一点,具体的实现时候:如果不符合条件,回溯到原来的某个b1的时候,则原来b1的b1……b1所置的数值都要清空掉,防止后面继续探索的时候跳过该该点从而造成的疏漏。
qq:79040875

[此贴子已经被作者于2005-6-22 10:57:02编辑过]



----------------解决方案--------------------------------------------------------

我的代码 可是结果有问题 找不出来 #define NULL 0 #define N 8

typedef struct Elemtype{ int row; int col; }Elemtype; /*栈元素*/

typedef struct Nodetype{ Elemtype data; struct Nodetype *next; }Nodetype,*Linktype; /*结点类型*/

typedef struct Stack{ Linktype top; int size; }Stack; /*栈类型*/

void push(Elemtype value,Stack S) { Linktype newnode;

newnode=(Linktype)malloc(sizeof(Nodetype));

newnode->data=value;

newnode->next=S.top;

S.top=newnode;

S.size++;

}/*存入数据*/

Elemtype pop(Stack S) { Elemtype temp; Linktype s;

if(S.top->next) { s=S.top; S.top=s->next; temp=s->data; free(s); S.size--; return temp; }

} /*取出数据*/

CreateStack(Stack S) {

S.top=(Linktype)malloc(sizeof(Nodetype));

S.top->next=NULL;

S.size=0;

} /*创建栈*/

int jump(int i,int j,int a[N][N]) {

if(i<N&&i>=0&&j<N&&j>=0&&a[i][j]==0) return 1; else return 0; } /*判断可行点*/

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

printf("\n");

} /*输出路径*/

void Delet(Stack S) { while(S.top) { Linktype temp; temp=S.top; S.top=temp->next; free(temp); } } /*输出路径*/

Stack S; Elemtype elem1, elem2,elem3;

main() { int HTry1[8]={-2,-1,1,2,2,1,-1,-2}; int HTry2[8]={1,2,2,1,-1,-2,-2,-1};

int board[N][N]={0};

int k,i,j,ti,tj,p=1,num=0;

printf("输入i,j的值:"); scanf("%d%d",&i,&j);

CreateStack(S);

elem1.row = i;

elem1.col = j;

push(elem1,S);

num++;

board[i][j] = num;

while( num>0 && num < 64) { for(k=0;k<8;k++) { i=i+HTry1[k]; j=j+HTry2[k];

if(jump(i,j,board[i][j])==1)

break;

} /*在点(i,j)周围8个点中寻找可扩展点*/

if(p==0) board[ti][tj]=0;

if(k<8) { elem2.row=i; elem2.col=j; push(elem2,S); num ++; board[i][j] = num; p=1; } /*在(i,j)周围八个点中找到的合适的入栈*/ else { elem2 = pop(S); ti=elem2.row; tj=elem2.col; p=0;

elem3=pop(S);

i=elem3.row; j=elem3.col; } /*8个点都不合适*/

}

output(board);

}


----------------解决方案--------------------------------------------------------
board[][]是用来存路径上的每个点?

[此贴子已经被作者于2005-6-22 13:27:32编辑过]



----------------解决方案--------------------------------------------------------
shi a
----------------解决方案--------------------------------------------------------
你的程序中怎么没有初始化一个棋盘呢?用一个矩阵来存储棋盘的每个点,我们可以把棋盘上的每个点都事先换算成数值(相当于坐标)。例如:char  chess[14][13]={1,1,1,1,1,1,1,1,1,1,1,1,1,
                                                                        1,1,1,1,1,1,1,1,1,1,1,1,1,
                                                                        1,1,0,0,0,0,0,0,0,0,0,1,1,
                                                                        1,1,0,0,0,0,0,0,0,0,0,1,1,
                                                                        1,1,0,0,0,0,0,0,0,0,0,1,1,
                                                                        1,1,0,0,0,0,0,0,0,0,0,1,1,
                                                                        1,1,0,0,0,0,0,0,0,0,0,1,1,
                                                                        1,1,0,0,0,0,0,0,0,0,0,1,1,
                                                                        1,1,0,0,0,0,0,0,0,0,0,1,1,
                                                                        1,1,0,0,0,0,0,0,0,0,0,1,1,
                                                                        1,1,0,0,0,0,0,0,0,0,0,1,1,
                                                                        1,1,0,0,0,0,0,0,0,0,0,1,1,
                                                                        1,1,1,1,1,1,1,1,1,1,1,1,1,
                                                                        1,1,1,1,1,1,1,1,1,1,1,1,1};
外层多加的两层1是给棋盘的一个“墙壁”,当然探索过的点就不能再用1了,建议用“-1”。当然如果你想在程序运行的时候自己手动初始化棋盘也没关系,反正又不是用我的手,这边只是给你个建议而已。
----------------解决方案--------------------------------------------------------
这论坛怎么搞的,我每次画东西都出错……,希望楼主自己看得懂ho,不关我事啊
----------------解决方案--------------------------------------------------------
  牛虻发的纯属灌水。大家千万别信
----------------解决方案--------------------------------------------------------
我快累死了
----------------解决方案--------------------------------------------------------

我也遇到这个问题了,想了一下午都米什么结果。
上面的代码看起来结构挺清晰的,但结果我调试了总有问题啊。
有谁能指出上面程序的漏洞吗?本菜鸟找不出
----------------解决方案--------------------------------------------------------
  相关解决方案