用栈求解迷宫，由于基础不牢，编得很乱，出不了正确结果，望高人指教。。。谢谢！！！ - 编程论坛

#2

遮天云2010-12-14 21:06

程序代码：

#define N 10
#define M 10
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
typedef struct node
{
    int row;
    int col;
    struct node *next;
}Mlink;

Mlink *Stack;
int MazePath()//寻找迷宫路径，若有则返回1，否则返回零
{
    int maze[N+2][M+2],i,j,x1,y1,x2,y2,r,c;
    //开始设置一圈障碍
    for(i=0;i<N+2;i++)//第零行设置障碍
        maze[0][i]=1;
    for(j=1;j<M+2;j++)//第零列设置障碍
        maze[j][0]=1;
    for(i=1;i<N+2;i++)//最后一行设置障碍
        maze[N+1][i]=1;
    for(j=1;j<M+1;j++)//最后一列设置障碍
        maze[j][M+1]=1;
    Mlink *p;
    printf("创建%d*%d迷宫矩阵\n",N,M);
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=M;j++)
        {
            scanf("%d",&maze[i][j]);
        //    fflush(stdin);
        }
    //    printf("\n");
    }
    printf("验证输出迷宫矩阵\n");
        for(i=0;i<N+2;i++)
        {
            for(j=0;j<M+2;j++)
                printf("%2d",maze[i][j]);
            printf("\n");
        }

    printf("输入迷宫的入口；\n");
    scanf("%d%d",&x1,&y1);
    fflush(stdin);

    Stack=NULL;
    p=(Mlink *)malloc(sizeof(Mlink));//将迷宫的入口位址入栈
    p->row=x1;
    p->col=y1;
    p->next=Stack;
    Stack=p;
    printf("验证%d\n",maze[1][1]);
        printf("输入迷宫的出口：\n");
    scanf("%d%d",&x2,&y2);
    fflush(stdin);
    maze[Stack->row][Stack->col]=1;//把入口位置设置为障碍，以阻止稍后的搜索在经过这个位置
    r=p->row;
    c=p->col;
    printf("x2=%d y2=%d\n",x2,y2);
    while(((r!=x2)||(c!=y2))&&Stack!=NULL)
    //考察当前位置的东南西北方向邻居是否有障碍
    //若没有，则沿着这个方向继续搜索，若都是障碍，则将栈顶元素出栈
    {
        if(maze[Stack->row][Stack->col+1]==0)
        {
            //printf("我");
            //printf("r=%d c=%d ",Stack->row,Stack->col+1);
            p=(Mlink *)malloc(sizeof(Mlink));
            p->row=Stack->row;
            p->col=Stack->col+1;
            r=p->row;
            c=p->col;
            p->next=Stack;
            Stack=p;
            maze[r][c]=1;//搜索过的位置设置为障碍，以阻止在后续搜索中在经过这个位置
        //    printf("maze[%d][%d]=%2d\n",r,c,maze[r][c]);
        //    getch();
            //fflush(stdin);
        }
        else if(maze[Stack->row][Stack->col-1]==0)
        {
        //    printf("爱");
        //    printf("r=%d c=%d ",Stack->row,Stack->col-1);
            p=(Mlink *)malloc(sizeof(Mlink));
            p->row=Stack->row;
            p->col=Stack->col-1;
            r=p->row;
            c=p->col;
            p->next=Stack;
            Stack=p;
            maze[r][c]=1;//搜索过的位置设置为障碍，以阻止在后续搜索中在经过这个位置
        //    printf("maze[%d][%d]=%2d\n",r,c,maze[r][c]);
        //    getch();
        //    fflush(stdin);

        }
        else if(maze[Stack->row+1][Stack->col]==0)
        {
            //printf("编");
        //    printf("r=%d c=%d ",Stack->row+1,Stack->col);
            p=(Mlink *)malloc(sizeof(Mlink));
            p->row=Stack->row+1;
            p->col=Stack->col;
            r=p->row;
            c=p->col;
            p->next=Stack;
            Stack=p;
            maze[r][c]=1;//搜索过的位置设置为障碍，以阻止在后续搜索中在经过这个位置
        //    printf("maze[%d][%d]=%2d\n",r,c,maze[r][c]);
        //    getch();
        //    fflush(stdin);
        }
        else if(maze[Stack->row-1][Stack->col]==0)
        {

            //printf("程");
        //    printf("r=%d c=%d ",Stack->row-1,Stack->col);
            p=(Mlink *)malloc(sizeof(Mlink));
            p->row=Stack->row-1;
            p->col=Stack->col;
            r=p->row;
            c=p->col;
            p->next=Stack;
            Stack=p;
            maze[r][c]=1;//搜索过的位置设置为障碍，以阻止在后续搜索中在经过这个位置
        //    printf("maze[%d][%d]=%2d\n",r,c,maze[r][c]);
        //    getch();
        //    fflush(stdin);
        }
        else //如果入到障碍说明路不通，栈顶元素出栈
        {
            //printf("牛\n");
        //    getch();
        //    fflush(stdin);
            p=Stack;
            Stack=Stack->next;
            free(p);
        }
    }
    if(Stack==NULL)//如果栈空，说明不存在通路
        return 0;
    else //否则存在通路
        return 1;
}
int main()
{
    int i;
    Mlink *p;
    i=MazePath();
    if(i==1)
    {
        p=Stack;
        printf("其中的一条路线为：\n");
        while(p!=NULL)
        {
            printf("%3d%3d\n",p->row,p->col);
            p=p->next;
        }
    }
    else
        printf("NO PATH!\n");
    return 0;
}

楼主看下我写的，在c板块也有高人写过这种题目

#3

tzhg5552010-12-14 22:42

这解法和我的想法不一样，我得好好消化去，谢谢啦！！！

#4

tzhg5552010-12-14 22:43

谁理解我想法的帮我改改，谢谢。。。。

#5

寒风中的细雨2010-12-15 22:41

把注释跟上去不然很难理解（最好保证方法是可行的）

#6

tzhg5552010-12-16 13:24

# include <stdio.h>
# include <malloc.h>
typedef struct
{
    int x,y;
    int flag; //flag=0,表示不可通过
}postype;

typedef struct
{
    int ord;//通道块在路径上的‘序号’
    postype seat;//通道块在迷宫中的‘坐标位置’
    int di;//此通道块走向下一通道块的‘方向’
}selemtype;//栈的元素类型

typedef struct
{
    postype a[20][20];
    int m;  //迷宫行数
    int n;  //迷宫列数
    int t;  //迷宫中可通过的块的个数
    postype start,end;
}mazetype;

typedef struct sqstack
{
    selemtype *top;
    selemtype *base;
    int stacksize;
}sqstack;
sqstack initstack(sqstack S)
{
    S.base=(selemtype *)malloc(100*sizeof(selemtype));
    S.top=S.base;
    S.stacksize=100;
    return S;
}
sqstack push(sqstack S,selemtype *e)
{
    *S.top=*e;
    S.top++;
    return S;
}
sqstack pop(sqstack S,selemtype *e)
{
    S.top--;
    *e=*S.top;
    return S;
}
stackempty(sqstack S)
{
    if(S.base==S.top)
        return 1;
    else
        return 0;
}
postype nextpos(postype Q,int n)//求下一步的位置
{
    switch(n)
    {
    case 1: Q.y++;break;
    case 2: Q.x++;break;
    case 3: Q.y--;break;
    case 4: Q.x--;break;
    }
    return Q;
}
mazetype creat(mazetype M)
{
    int i,j,p,q;
    scanf("%d%d%d",&M.m,&M.n,&M.t);
    for(i=0;i<=M.m;i++)
        for(j=0;j<=M.n;j++)
        {
                M.a[i][j].flag=0;
        }
    for(i=0;i<M.t;i++)
    {
        scanf("%d%d",&p,&q);
        scanf("%d",&M.a[p][q].flag);//输入迷宫可通过位置的坐标
    }
    for(i=0;i<=M.m;i++)//输出迷宫
    {
        for(j=0;j<=M.n;j++)
        {
            if(M.a[i][j].flag==0)
                printf("* ");
            else
                printf("  ");
        }
        printf("\n");
    }
    return M;
}
void main()
{
   sqstack S;
   mazetype maze;
   int curstep=1; //走第一步
   selemtype *e;
   postype curpos;
   e=(selemtype *)malloc(sizeof(selemtype));
   maze=creat(maze);
   scanf("%d%d%d%d%d%d",&maze.start.x,&maze.start.y,&maze.start.flag,&maze.end.x,&maze.end.y,&maze.end.flag);
   S=initstack(S);
   curpos=maze.start;
   do
   {
       if(maze.a[curpos.x][curpos.y].flag)  //当前位置可通过
       {
           curpos.flag=0;  //留下足迹
           e->ord=curstep;
           e->seat=curpos;
           e->di=1;
           S=push(S,e);
           if(curpos.x==maze.end.x&&curpos.y==maze.end.y)
               break;  //找到终点
           curpos=nextpos(curpos,1);
           curstep++;  //探索下一步
       }
       else  //当前位置不可通过
       {
           if(!stackempty(S))
           {
               S=pop(S,e);
               while(e->di==4&&!stackempty(S))
               {
                   e->seat.flag=0;
                   S=pop(S,e);
               }
               if(e->di<4)
               {
                   e->di++;
                   S=push(S,e);
                   curpos=nextpos(e->seat,e->di);
               }
           }
       }
   }while(!stackempty(S));
   while(!stackempty(S))  //输出栈存的路径
   {
       S=pop(S,e);
       printf("(%d,%d)",e->seat.x,e->seat.y);
   }
}

#7

tzhg5552010-12-16 13:30

比如我可以输入
4 4 5
1 1 1
2 1 1
3 1 1
3 2 1
3 3 1
他就出现迷宫
再输入
1 1 1
3 3 1
就可以有路径
但是，复杂的迷宫
如：
5 7 12
1 1 1
1 4 1
2 1 1
2 4 1
2 5 1
2 6 1
3 3 1
3 2 1
3 3 1
3 4 1
4 1 1
5 1 1
就不行了。。。

#8

tzhg5552010-12-17 13:09

# include <stdio.h>
# include <malloc.h>
typedef struct
{
    int x,y;
    int flag; //flag=0,表示不可通过
}postype;

typedef struct
{
    int ord;//通道块在路径上的‘序号’
    postype seat;//通道块在迷宫中的‘坐标位置’
    int di;//此通道块走向下一通道块的‘方向’
}selemtype;//栈的元素类型

typedef struct
{
    postype a[20][20];
    int m;  //迷宫行数
    int n;  //迷宫列数
    int t;  //迷宫中可通过的块的个数
    postype start,end;
}mazetype;

typedef struct sqstack
{
    selemtype *top;
    selemtype *base;
    int stacksize;
}sqstack;
sqstack initstack(sqstack S)
{
    S.base=(selemtype *)malloc(100*sizeof(selemtype));
    S.top=S.base;
    S.stacksize=100;
    return S;
}
sqstack push(sqstack S,selemtype *e)
{
    *S.top=*e;
    S.top++;
    return S;
}
sqstack pop(sqstack S,selemtype *e)
{
    S.top--;
    *e=*S.top;
    return S;
}
stackempty(sqstack S)
{
    if(S.base==S.top)
        return 1;
    else
        return 0;
}
postype nextpos(postype Q,int n)//求下一步的位置
{
    switch(n)
    {
    case 1: Q.y++;break;
    case 2: Q.x++;break;
    case 3: Q.y--;break;
    case 4: Q.x--;break;
    }
    return Q;
}
mazetype creat(mazetype M)
{
    int i,j,p,q;
    scanf("%d%d%d",&M.m,&M.n,&M.t);
    for(i=0;i<=M.m;i++)
        for(j=0;j<=M.n;j++)
        {
                M.a[i][j].flag=0;
        }
    for(i=0;i<M.t;i++)
    {
        scanf("%d%d",&p,&q);
        scanf("%d",&M.a[p][q].flag);//输入迷宫可通过位置的坐标
    }
    for(i=0;i<=M.m;i++)//输出迷宫
    {
        for(j=0;j<=M.n;j++)
        {
            if(M.a[i][j].flag==0)
                printf("* ");
            else
                printf("  ");
        }
        printf("\n");
    }
    return M;
}
void main()
{
   sqstack S;
   mazetype maze;
   int curstep=1; //走第一步
   selemtype *e;
   postype curpos;
   e=(selemtype *)malloc(sizeof(selemtype));
   maze=creat(maze);
   scanf("%d%d%d%d%d%d",&maze.start.x,&maze.start.y,&maze.start.flag,&maze.end.x,&maze.end.y,&maze.end.flag);
   S=initstack(S);
   curpos=maze.start;
   do
   {
       if(maze.a[curpos.x][curpos.y].flag)  //当前位置可通过
       {
          maze.a[curpos.x][curpos.y].flag=0;  //留下足迹
           e->ord=curstep;
           e->seat=curpos;
           e->di=1;
           S=push(S,e);
           if(curpos.x==maze.end.x&&curpos.y==maze.end.y)
               break;  //找到终点
           curpos=nextpos(curpos,1);
           curstep++;  //探索下一步
       }
       else  //当前位置不可通过
       {
           if(!stackempty(S))
           {
               S=pop(S,e);
               while(e->di==4&&!stackempty(S))
               {
                   e->seat.flag=0;
                   S=pop(S,e);
               }
               if(e->di<4)
               {
                   e->di++;
                   S=push(S,e);
                   curpos=nextpos(e->seat,e->di);
               }
           }
       }
   }while(!stackempty(S));
   while(!stackempty(S))  //输出栈存的路径
   {
       S=pop(S,e);
       printf("(%d,%d)",e->seat.x,e->seat.y);
   }
}
调试的时候发现错哪了，现在改回来了，谢谢大家哈！！！

#9

许玉飞嵩2014-06-06 15:42

回复 2 楼遮天云

你好，可以解读一些这个程序吗？谢啦