| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2661 人关注过本帖
标题:迷宫求解问题,运行不出来,求大神给看看。
只看楼主 加入收藏
春风吹又吹
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2016-10-22
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:9 
迷宫求解问题,运行不出来,求大神给看看。
#include<stdio.h>
#include<malloc.h>
#define M 8
#define N 10
typedef int elemtype;
typedef struct{
elemtype *base;
elemtype *top;
int stacksize;
}sqstack;
typedef struct{
    int a,b,dir;
}offsets;
typedef struct{
    int x,y,dr;
}elemstack;
int initstack(sqstack &s)
{
    s.base=(elemtype *)malloc(80 *sizeof(elemtype));
    if(!s.base) return 0;
    s.top=s.base;
    s.stacksize=80;
    return 1;
}
int push(sqstack &s,elemstack &temp)
{
if(s.top-s.base>=s.stacksize)
    {    s.base=(elemtype *)realloc(s.base,(s.stacksize+10)*sizeof(elemtype));
        if(!s.base) return 0;
        s.top=s.base+s.stacksize;
        s.stacksize+=10;
    }
    *s.top=temp;
    s.top++;
    return 1;

}
elemtype pop(sqstack &s,elemstack &temp)
{
    if(s.top==s.base) return 0;
    s.top--;
    *s.top=temp;
    return 1;
}

void path(int maze[M][N],offsets move[4])
{
    elemstack temp;
    sqstack s;
    int g,h,d,i,j;
    int    mark[1][0]=2;
    initstack(s);
    int p=6,q=8;
    temp.x=1;temp.y=1;temp.dr=1;
    push(s,temp);
    while(s.top!=s.base)
    {
        pop(s,temp);
        i=temp.x;j=temp.y;d=temp.dr;
        while(d<=4)
        {
            g=i+move[d].a;h=j+move[d].b;
            if(g==p&&h==q)
            {
                printf("(%d,%d)",p,q);
                while(s.top!=s.base)
                {
                    pop(s,temp);
                    printf("(%d,%d)",temp.x,temp.y);
                }
            }
            if(!maze[g][h]&&!mark[g][h])
            {
                mark[g][h]=2;
                temp.x=i;temp.y=j;temp.dr=d;
                push(s,temp);
                i=g;j=h;d=1;
            }
            else d++;

        }
    }   
printf("no path in maze!");
}


int main()
{
    int maze[M][N]={
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 0, 0, 1, 1, 0, 1, 1, 1, 1,
    1, 1, 0, 1, 0, 1, 1, 1, 1, 1,
    1, 1, 0, 0, 0, 0, 0, 0, 1, 1,
    1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
    1, 1, 0, 0, 1, 0, 0, 0, 0, 1,
    1, 0, 1, 1, 0, 1, 1, 1, 0, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    };
/*    int i,j;
    for(i=0;i<m;i++)
    {for(j=0;j<n;j++)
        {
            printf("%d  ",a[i][j]);
        }
    printf("\n");
    }
*/
    offsets move[4]={{1,0,1}{0,1,2}{-1,0,3}{0,-1,4}};
     path(maze[][], move[]);
/*    int i,j;
    for(i=0;i<m;i++)
    {for(j=0;j<n;j++)
        {
            printf("%d  ",a[i][j]);
        }
    printf("\n");
    }
*/


    return 0;
}
搜索更多相关主题的帖子: return include 
2016-10-24 20:54
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:10 
不是很理解称需要解决什么样的问题,会有什么输入,预期的输出是什么。简单检查了一下你的语法,找出错误如下:





程序代码:
#include<stdio.h>
#include<malloc.h>
#define M 8
#define N 10
typedef int elemtype;
typedef struct{
elemtype *base;
elemtype *top;
int stacksize;
}sqstack;
typedef struct{
    int a,b,dir;
}offsets;
typedef struct{
    int x,y,dr;
}elemstack;
int initstack(sqstack &s)
{
    s.base=(elemtype *)malloc(80 *sizeof(elemtype));
    if(!s.base) return 0;
    s.top=s.base;
    s.stacksize=80;
    return 1;
}
int push(sqstack &s,elemstack &temp)
{
if(s.top-s.base>=s.stacksize)
    {    s.base=(elemtype *)realloc(s.base,(s.stacksize+10)*sizeof(elemtype));
        if(!s.base) return 0;
        s.top=s.base+s.stacksize;
        s.stacksize+=10;
    }
    *s.top=temp;//类型不匹配,s.top只能接收一个int,temp是拥有3个int的结构体

    s.top++;
    return 1;

}
elemtype pop(sqstack &s,elemstack &temp)
{
    if(s.top==s.base) return 0;
    s.top--;
    *s.top=temp;//类型不匹配,同上

    return 1;
}

void path(int maze[M][N],offsets move[4])
{
    elemstack temp;
    sqstack s;
    int g,h,d,i,j;
    int    mark[1][0]=2;//这里我没看懂,不擅改了,如果是要初始化的话必须用花括号打包起来才行

    initstack(s);
    int p=6,q=8;
    temp.x=1;temp.y=1;temp.dr=1;
    push(s,temp);
    while(s.top!=s.base)
    {
        pop(s,temp);
        i=temp.x;j=temp.y;d=temp.dr;
        while(d<=4)
        {
            g=i+move[d].a;h=j+move[d].b;
            if(g==p&&h==q)
            {
                printf("(%d,%d)",p,q);
                while(s.top!=s.base)
                {
                    pop(s,temp);
                    printf("(%d,%d)",temp.x,temp.y);
                }
            }
            if(!maze[g][h]&&!mark[g][h])
            {
                mark[g][h]=2;
                temp.x=i;temp.y=j;temp.dr=d;
                push(s,temp);
                i=g;j=h;d=1;
            }
            else d++;

        }
    }  

printf("no path in maze!");
}


int main()
{
    int maze[M][N]={
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 0, 0, 1, 1, 0, 1, 1, 1, 1,
    1, 1, 0, 1, 0, 1, 1, 1, 1, 1,
    1, 1, 0, 0, 0, 0, 0, 0, 1, 1,
    1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
    1, 1, 0, 0, 1, 0, 0, 0, 0, 1,
    1, 0, 1, 1, 0, 1, 1, 1, 0, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    };
/*    int i,j;
    for(i=0;i<m;i++)
    {for(j=0;j<n;j++)
        {
            printf("%d  ",a[i][j]);
        }
    printf("\n");
    }
*/
    offsets move[4]={{1,0,1},{0,1,2},{-1,0,3},{0,-1,4}};//已改,每个节点信息之间也需要用逗号隔开

     path(maze, move);//已改,去掉中括号,直接把数组名称传入即可

/*    int i,j;
    for(i=0;i<m;i++)
    {for(j=0;j<n;j++)
        {
            printf("%d  ",a[i][j]);
        }
    printf("\n");
    }
*/


    return 0;
} 




φ(゜▽゜*)♪
2016-10-25 06:08
春风吹又吹
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2016-10-22
收藏
得分:0 
你好,我这个程序是要利用栈的有关知识解决迷宫问题,调用path函数同时输出迷宫中从入口1.1位置到出口6.8的依次经过的位置,你帮忙给看看path这个函数,或者帮我编一个函数来解决迷宫问题,谢谢😊
2016-10-25 12:07
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:5 
不好意思,我知道这是迷宫问题,但是我还是不知道要怎么走?

1.给了一个二维数组{x,y},是用0,1表示结点x和结点y是否存在通路?还是说就是基于这个二维矩阵1表示能走,0表示墙,然后在矩阵内上下左右移动?

2.typedef struct{
    int a,b,dir;//这里的dir表示什么?半径?
}offsets;

3.你是只需要随便输出任意一条路径验证是否存在通路即可还是要找到最短路径?又或者当存在多条路径可能时需要全部遍历输出,如果这样,1-2-3-4和1-3-2-4算不算一条路径?需不需要分成两次输出?

...迷宫问题应该就是“图的联通”问题,你可以直接百度这个关键字“图的联通”,你将会找到好几个算法(这个题目是已知起点和终点的)。根据你所面对的问题实际情况,酌情选择。我还是没看懂你所面临的问题是啥样。不知道“解决什么样的问题,会有什么输入,预期的输出是什么”,不能替你选择。

φ(゜▽゜*)♪
2016-10-25 13:44
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:3 
如果有题目,把链接贴上来。我们直接看题目会比较容易理解些。

φ(゜▽゜*)♪
2016-10-25 13:45
春风吹又吹
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2016-10-22
收藏
得分:0 
1.学x,y代表二维数组的坐标,0代表能走,1代表墙,dir代表上下左右四个方向
2.我设计的maze数组中因为0代表能走的的位置,所以从起点1.1到终点6.8只有一条路能走,然后再利用每次经过的位置和方向入栈先存着,再继续探索下一个为0的位置再入栈,直到找到终点位置,然后再让栈中的数据依次出栈且输出位置。
3.我对这个迷宫的输出没什么要求,只要能最后输出这个迷宫的起点到终点的依次经过的位置就行了
2016-10-25 15:51
春风吹又吹
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2016-10-22
收藏
得分:0 
1.学x,y代表二维数组的坐标,0代表能走,1代表墙,dir代表上下左右四个方向
2.我设计的maze数组中因为0代表能走的的位置,所以从起点1.1到终点6.8只有一条路能走,然后再利用每次经过的位置和方向入栈先存着,再继续探索下一个为0的位置再入栈,直到找到终点位置,然后再让栈中的数据依次出栈且输出位置。
3.我对这个迷宫的输出没什么要求,只要能最后输出这个迷宫的起点到终点的依次经过的位置就行了
2016-10-25 15:52
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:2 

程序代码:
void path(int maze[M][N],offsets move[4])
{
    elemstack temp;
    sqstack s;
    int g,h,d,i,j;
    int    mark[1][0]=2;

    initstack(s);
    int p=6,q=8;
    temp.x=1;temp.y=1;temp.dr=1;//初始化迷宫入口结点(1,1),初始化方向向右
    push(s,temp);
    while(s.top!=s.base)
    {
        pop(s,temp);
        i=temp.x;j=temp.y;d=temp.dr;
        while(d<=4)//遍历四个方向
        {
            g=i+move[d].a;h=j+move[d].b;
            if(g==p&&h==q)//判断是不是到终点了。但在此之前并没有判断(g,h)或者(x,y)是0还是1,是道路还是墙
            {
                printf("(%d,%d)",p,q);
                while(s.top!=s.base)//弹出站内剩余元素,不过这栈内的元素真的是路径吗?貌似站内保存的应该是一些还没走过的结点吧
                {
                    pop(s,temp);
                    printf("(%d,%d)",temp.x,temp.y);
                }
            }
            if(!maze[g][h]&&!mark[g][h])//mark【1】【0】,mark[g][h],他一定越界了。
            {
                mark[g][h]=2;//貌似mark(g,h)=2是为了标记(g,h)这个点为踩过的点。
                temp.x=i;temp.y=j;temp.dr=d;
                push(s,temp);//temp.(i,j)不是刚刚遍历过,你又把他压回栈中做什么?打算一会再走一遍?
                i=g;j=h;d=1;//如果你是为了一会输出路径使用。那么我请问你从(1,1)出发以后什么时候能到达(1,2)(2,1)?Never.
            }
            else d++;

        }
    } 


printf("no path in maze!");
}

我猜你的程序会在 while(s.top!=s.base){..}部分进入死循环,而栈内的元素永远只有一个(1,1),他不断地出栈、入栈、不死不休。。。

程序代码:
#include<stdio.h>
#include<malloc.h>
#define M 8
#define N 10

typedef struct {
    int x,y;
} elemstack;
typedef struct {
    elemstack *base;
    elemstack *top;
    int stacksize;
} sqstack;
int maze[M][N]= {
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 0, 0, 1, 1, 0, 1, 1, 1, 1,
    1, 1, 0, 1, 0, 1, 1, 1, 1, 1,
    1, 1, 0, 0, 0, 0, 0, 0, 1, 1,
    1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
    1, 1, 0, 0, 1, 0, 0, 0, 0, 1,
    1, 0, 1, 1, 0, 1, 1, 1, 0, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
};

int initstack(sqstack &s) {
    s.base=(elemstack *)malloc(80 *sizeof(elemstack));
    if(!s.base) return 0;
    s.top=s.base;
    s.stacksize=80;
    return 1;
}
int push(sqstack &s,elemstack &temp) {
    if(s.top-s.base>=s.stacksize) {
        s.base=(elemstack *)realloc(s.base,(s.stacksize+10)*sizeof(elemstack));
        if(!s.base) return 0;
        s.top=s.base+s.stacksize;
        s.stacksize+=10;
    }
    *s.top=temp;

    s.top++;
    return 1;

}
int pop(sqstack &s,elemstack &temp) {
    if(s.top==s.base) return 0;
    s.top--;
    temp=*s.top;

    return 1;
}

void path(int maze[M][N],int move[4][2]) {
    elemstack temp;
    sqstack Unused;
    initstack(Unused);

    int g,h,d,i,j;

    elemstack End= {6,8};
    maze[End.x][End.y]=5;//和算法无关,只是想让 终点在输出的时候凸显出了

    temp.x=1;
    temp.y=1;
    push(Unused,temp);

    while(Unused.top!=Unused.base) {
        pop(Unused,temp);

        i=temp.x;
        j=temp.y;
        maze[i][j]=2;
        for(d=0; d<4; d++) {
            g=i+move[d][0];
            h=j+move[d][1];
            if(g==End.x&&h==End.y) { //找到终点就弹出整个堆栈

                printf("Yes,we found the path!\n");
                printf("\n----\n");
                return ;
            } else if(!maze[g][h]) {
                maze[g][h]=2;
                temp.x=g;
                temp.y=h;
                push(Unused,temp);
            }

        }
    }

    printf("no path in maze!");
}


int main() {

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

    int move[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};

    path(maze, move);


    for(i=0; i<M; i++) {
        for(j=0; j<N; j++) {
            printf("%d  ",maze[i][j]);
        }
        printf("\n");
    }
    return 0;
}
图片附件: 游客没有浏览图片的权限,请 登录注册




[此贴子已经被作者于2016-10-26 09:18编辑过]


φ(゜▽゜*)♪
2016-10-26 08:12
春风吹又吹
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2016-10-22
收藏
得分:0 
哇塞,厉害,谢谢你啦😄,我再理解理解看看
2016-10-26 11:04
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:0 
回复 9楼 春风吹又吹
其实这个方法通常适用于仅判断“是否存在通路可行”。属于是“深度优先”算法的一次应用。

我给你输出的迷宫路径是有很多冗余的,他们只是程序走过的每一个脚印,但不是最短路径,很多结点 都是不需要走的。要想把那些多余的结点去掉有点麻烦。

φ(゜▽゜*)♪
2016-10-27 11:13
快速回复:迷宫求解问题,运行不出来,求大神给看看。
数据加载中...
 
   



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

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