广度搜索问题

独一无②

今天在书上看到一则例题，走迷宫，输入m行n列构成的迷宫，入口（1,1），出口（m,n）
迷宫输入 1表示墙，不可走，0表示通
给出的是伪代码，不全，然后我尝试写出完整代码，但是失败了

/*
mark数组用于标记是否被访问过，已访问标记1，否则标记0 
maze数组就是要输入的迷宫
结构体que是搜索中用到的队列，s是一个栈，具体我现在也没明白干什么用 
*/
#include<stdio.h>
int mark[12][12],maze[12][12];
int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int m,n,h=0,t=0,top=0;
struct
{
        int x,y;//当前结点位置 
        int px,py;//到达当前结点所经过的结点 
}que[100],s[100];
int seekpath(int x,int y)//此函数和上面结构体是书本给出的伪代码 
{
        int cx,cy,cpx,cpy,dx,dy,i;
        que[t].x=x;que[t].y=y;
        que[t].px=0;que[t].py=0;
        t++;                    //起始点进入队列 
        s[top].x=x;s[top].y=y;
        s[top].px=0;s[top].py=0;
        top++;                 //起始点进入栈 
        while(h != t)
        {
                cx=que[h].x;
                cy=que[h].y;    //取队列元素 
                cpy=que[h].px;
                cpy=que[h].py;
                h++;           //出队列 
                if(cx==m && cy==n)
                   break;//找到出口 
        s[top].x=cx;s[top].y=cy;//经过结点入栈 
                s[top].px=cpx;s[top].py=cpy;
                top++;                //经过位置入栈 
                for(i=0;i<4;i++)//对4个方向进行试探 
                {
                        dx=cx+move[i][0];//计算新结点位置 
                        dy=cy+move[i][1];
                        if(maze[dx][dy]==0 && mark[dx][dy]==0)
                        {                  //如果可以走 
                                mark[dx][dy]=1;//标记此位置 
                                que[t].x=dx;que[t].y=dy;
                                que[t].px=cx;que[t].py=cy;
                                t++;          //进入队列 
                        }
                }
        }//以下代码就看不懂了，不知道是不是输出，但是不行 
        printf("%d,%d\n",cx,cy);
        while(top != 0)   //书上说是查找走过的路径 
        {
                if(cpx==s[top].x && cpy==s[top].y)
                {
                        printf("%d,%d\n",cpx,cpy);
                        cpx=s[top].px;cpy=s[top].py;
                }
                top--;
        }
        return 0;
}
int main()
{
        int i,j;
        scanf("%d%d",&m,&n);
        for(i=0;i<=m+1;i++)//初始化，在迷宫的外层要多加一层墙，防出界 
        {
                for(j=0;j<=n+1;j++)
                {
                        maze[i][j]=1;
                        mark[i][j]=0;//所有点都设置未访问 
                }
        }
        for(i=1;i<=m;i++)//输入迷宫 
           for(j=1;j<=n;j++)
              scanf("%d",&maze[i][j]);
    seekpath(1,1);//调用 
    
}

主要是对伪代码中 这段不理解，感觉不像是输出

printf("%d,%d\n",cx,cy);
        while(top != 0)   //书上说是查找走过的路径 
        {
                if(cpx==s[top].x && cpy==s[top].y)
                {
                        printf("%d,%d\n",cpx,cpy);
                        cpx=s[top].px;cpy=s[top].py;
                }
                top--;
        }

有个样例

6 8
0 0 1 0 0 0 1 1
1 0 0 0 1 0 0 0
0 0 0 1 1 0 1 1
1 1 0 1 0 0 0 0
0 0 0 0 0 1 0 1
1 0 1 0 0 0 0 0

输出路径：：
(1,1) (1,2) (2,2) (2,3) (3,3) (4,3) (5,3) (5,4) (5,5) (6,5) (6,6) (6,7) (6,8)

ko12

第28行，cpy改为cpx

ko12

50行到58行之间的代码是将保存在栈s里的路径打印出来

ko12

50行到58行之间的代码是将保存在栈s里的路径打印出来

ko12

在23行和24行之间加mark[x][y]=1;，将起始位置标记为已访问

独一无②

ko12 发表于 2016-1-29 12:38
在23行和24行之间加mark[x][y]=1;，将起始位置标记为已访问

O(∩_∩)O谢谢，可以了，太感谢了，虽然栈那段代码还是不太理解

ko12

独一无② 发表于 2016-1-29 13:50
O(∩_∩)O谢谢，可以了，太感谢了，虽然栈那段代码还是不太理解

不用谢。