| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2196 人关注过本帖
标题:求助遍历棋盘
只看楼主 加入收藏
Karryu
Rank: 1
等 级:新手上路
帖 子:37
专家分:0
注 册:2016-5-5
结帖率:90%
收藏
已结贴  问题点数:15 回复次数:3 
求助遍历棋盘
马踏棋盘

程序代码:
#include <stdio.h>
#include <stdlib.h>

typedef struct              //结点类型
 {
    int num1;
    int num2;
    struct node *prior;
    struct node *next;

 }node;

typedef struct            //走法数组类型
{
    int m;
    int n;
}array; 

typedef struct             //栈的类型
{
    int row;
    int col;
}stack;

int main()          
{
    int i,j,k,l;
    int a,b=0;
    node *head,*p,*ptr;
    int flag[9][9]={0};    
    array po[9];
    stack S[65];                           //初始化栈
    int top=0;
    S[0].row=S[0].col=0;
    head=(node *)malloc(sizeof(node));     //初始化链表
    head->num1=head->num2=NULL;
    head->prior=NULL;
    head->next=NULL;
    p=head;
    printf("请输入起点坐标:i,j\n");
    scanf("%d,%d",&i,&j);
    top++;
    S[top].row=i;                           //已遍历方格入栈
    S[top].col=j;
    flag[i][j]=1;                           //标记遍历方格
    ptr=(node *)malloc(sizeof(node));       //建立表头结点
    ptr->num1=i;
    ptr->num2=j;
    ptr->prior=p;
    ptr->next=NULL;
    p=ptr;
    do
    {
if(top==50)
{
    printf("hahah\n");
}

        printf("%d,%d->",S[top].row,S[top].col);
    for(k=1;k<9;k++)                     //8种走法
    {
        if(k==1||k==2) po[k].m=i-1;
        if(k==3||k==4) po[k].m=i+1;
        if(k==5||k==6) po[k].m=i-2;
        if(k==7||k==8) po[k].m=i+2;
        if(k==1||k==3) po[k].n=j-2;
        if(k==2||k==4) po[k].n=j+2;
        if(k==5||k==7) po[k].n=j-1;
        if(k==6||k==8) po[k].n=j+1;
    }
    if((a!=0)&&(b!=0))                  //发生回溯的情况
    {       
            for(k=1;k<9;k++)
            {
                if((po[k].m==a)&&(po[k].n==b)) 
                {a=0;
                 b=0;
                 for(l=1;l<(k+1);l++)
                 {
                    po[l].m=0;
                    po[l].n=0;
                 }
                 break;
                }
            }
        
    }
    for(k=1;k<9;k++)                     //筛选不可行走法
    {
        if((po[k].m<1)||(po[k].m>8)||(po[k].n<1)||(po[k].n>8))
        {po[k].m=0;
        po[k].n=0;}
        if(flag[po[k].m][po[k].n]==1)
        {po[k].m=0;
          po[k].n=0;}
    }

    for(k=1;k<9;k++)
    {
        if(flag[po[k].m][po[k].n]==0&&po[k].m!=0)      
        {
            top++;
            i=po[k].m;
            j=po[k].n;
            S[top].row=i;
            S[top].col=j;
            flag[i][j]=1;
            ptr=(node *)malloc(sizeof(node));
            ptr->num1=i;
            ptr->num2=j;
            ptr->prior=p;
            ptr->next=NULL;
            p=ptr;
            break;
        }
    }   
    if(k==9)          //当无可行路径时,回溯
    {
        a=i;
        b=j;
        flag[i][j]=0;
          p=p->prior;
        free(ptr);
        ptr=p;
         top--;
        if(top==0)
        {
            printf("\n无法遍历棋盘!\n");
            system("pause");
            return 0;
        }
           i=S[top].row;
        j=S[top].col;
    }
    }while(0<top<65);
    
    if(top==64)
    {   ptr->next=NULL;
        p=head;
        for(l=1;l<64;l++)
        {  
            p=p->next;
            printf("(%d,%d)",p->num1,p->num2);
        }
    }
    system("pause");
    return 0;
}




回溯的代码是不是有问题,好像会出现重复的情况,得不出结果
用这种方式能解决问题吗 可以改出来吗
搜索更多相关主题的帖子: color 
2016-12-10 17:34
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:15 
思路没问题的,也就是重复操作太多所以得出结果会慢一些这么一点瑕疵

得不出结果原因是do while条件恒真

while(0<top<65) --> while((0<top)<65) --> while(1<65) --> while(true)


再者top取值有64种(0 - 63)可能,所以正确的写法是 while (0 < top && top < 64)

哦,你的链表用的不对,next 域从未赋值过,所以输出那肯定会有问题

而且已经有stack了,完全可以删除链表部分。打印stack即可

ps:不要放弃数组的0域,那么大个空间弃用怪可惜的

[此贴子已经被作者于2016-12-11 13:57编辑过]



[fly]存在即是合理[/fly]
2016-12-11 13:49
Karryu
Rank: 1
等 级:新手上路
帖 子:37
专家分:0
注 册:2016-5-5
收藏
得分:0 
回复 2楼 azzbcc
链表加上这句就没问题了吧?    p->next=ptr;
主要是不知道回溯的代码是不是哪里错了 走过不行的之后还会再走
运行了很久还是没有结果

[此贴子已经被作者于2016-12-13 15:24编辑过]

2016-12-13 14:50
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
链表加上这句就没问题了吧?    p->next=ptr;

恩,两个地方要加

主要是不知道回溯的代码是不是哪里错了 走过不行的之后还会再走 运行了很久还是没有结果

你的思路比较懒,穷举的频率较多,所以运行很慢,但是要出结果还是没问题的

我这边测试,把while条件改掉后,运行 40s 左右显示结果




[fly]存在即是合理[/fly]
2016-12-13 16:22
快速回复:求助遍历棋盘
数据加载中...
 
   



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

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