注册 登录
编程论坛 → 数据结构与算法

迷宫求解问题，运行不出来，求大神给看看。

春风吹又吹 发布于 2016-10-24 20:54， 2722 次点击
#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;
}
9 回复
#2
书生牛犊2016-10-25 06:08
不是很理解称需要解决什么样的问题，会有什么输入，预期的输出是什么。简单检查了一下你的语法，找出错误如下：





程序代码：
#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;
}



#3
春风吹又吹2016-10-25 12:07
你好，我这个程序是要利用栈的有关知识解决迷宫问题，调用path函数同时输出迷宫中从入口1.1位置到出口6.8的依次经过的位置，你帮忙给看看path这个函数，或者帮我编一个函数来解决迷宫问题，谢谢😊
#4
书生牛犊2016-10-25 13:44
不好意思，我知道这是迷宫问题，但是我还是不知道要怎么走？

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算不算一条路径？需不需要分成两次输出？

...迷宫问题应该就是“图的联通”问题，你可以直接百度这个关键字“图的联通”，你将会找到好几个算法（这个题目是已知起点和终点的）。根据你所面对的问题实际情况，酌情选择。我还是没看懂你所面临的问题是啥样。不知道“解决什么样的问题，会有什么输入，预期的输出是什么”，不能替你选择。
#5
书生牛犊2016-10-25 13:45
如果有题目，把链接贴上来。我们直接看题目会比较容易理解些。
#6
春风吹又吹2016-10-25 15:51
1.学x，y代表二维数组的坐标，0代表能走，1代表墙，dir代表上下左右四个方向
2.我设计的maze数组中因为0代表能走的的位置，所以从起点1.1到终点6.8只有一条路能走，然后再利用每次经过的位置和方向入栈先存着，再继续探索下一个为0的位置再入栈，直到找到终点位置，然后再让栈中的数据依次出栈且输出位置。
3.我对这个迷宫的输出没什么要求，只要能最后输出这个迷宫的起点到终点的依次经过的位置就行了
#7
春风吹又吹2016-10-25 15:52
1.学x，y代表二维数组的坐标，0代表能走，1代表墙，dir代表上下左右四个方向
2.我设计的maze数组中因为0代表能走的的位置，所以从起点1.1到终点6.8只有一条路能走，然后再利用每次经过的位置和方向入栈先存着，再继续探索下一个为0的位置再入栈，直到找到终点位置，然后再让栈中的数据依次出栈且输出位置。
3.我对这个迷宫的输出没什么要求，只要能最后输出这个迷宫的起点到终点的依次经过的位置就行了
#8
书生牛犊2016-10-26 08:12

程序代码：
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编辑过]
#9
春风吹又吹2016-10-26 11:04
哇塞，厉害，谢谢你啦😄，我再理解理解看看
#10
书生牛犊2016-10-27 11:13
回复 9楼 春风吹又吹
其实这个方法通常适用于仅判断“是否存在通路可行”。属于是“深度优先”算法的一次应用。

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