广度搜索问题

独一无②

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

1. /*
   
2. mark数组用于标记是否被访问过，已访问标记1，否则标记0
   
3. maze数组就是要输入的迷宫
   
4. 结构体que是搜索中用到的队列，s是一个栈，具体我现在也没明白干什么用
   
5. */
   
6. #include<stdio.h>
   
7. int mark[12][12],maze[12][12];
   
8. int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
   
9. int m,n,h=0,t=0,top=0;
   
10. struct
    
11. {
    
12.         int x,y;//当前结点位置
    
13.         int px,py;//到达当前结点所经过的结点
    
14. }que[100],s[100];
    
15. int seekpath(int x,int y)//此函数和上面结构体是书本给出的伪代码
    
16. {
    
17.         int cx,cy,cpx,cpy,dx,dy,i;
    
18.         que[t].x=x;que[t].y=y;
    
19.         que[t].px=0;que[t].py=0;
    
20.         t++;                    //起始点进入队列
    
21.         s[top].x=x;s[top].y=y;
    
22.         s[top].px=0;s[top].py=0;
    
23.         top++;                 //起始点进入栈
    
24.         while(h != t)
    
25.         {
    
26.                 cx=que[h].x;
    
27.                 cy=que[h].y;    //取队列元素
    
28.                 cpy=que[h].px;
    
29.                 cpy=que[h].py;
    
30.                 h++;           //出队列
    
31.                 if(cx==m && cy==n)
    
32.                    break;//找到出口
    
33.         s[top].x=cx;s[top].y=cy;//经过结点入栈
    
34.                 s[top].px=cpx;s[top].py=cpy;
    
35.                 top++;                //经过位置入栈
    
36.                 for(i=0;i<4;i++)//对4个方向进行试探
    
37.                 {
    
38.                         dx=cx+move[i][0];//计算新结点位置
    
39.                         dy=cy+move[i][1];
    
40.                         if(maze[dx][dy]==0 && mark[dx][dy]==0)
    
41.                         {                  //如果可以走
    
42.                                 mark[dx][dy]=1;//标记此位置
    
43.                                 que[t].x=dx;que[t].y=dy;
    
44.                                 que[t].px=cx;que[t].py=cy;
    
45.                                 t++;          //进入队列
    
46.                         }
    
47.                 }
    
48.         }//以下代码就看不懂了，不知道是不是输出，但是不行
    
49.         printf("%d,%d\n",cx,cy);
    
50.         while(top != 0)   //书上说是查找走过的路径
    
51.         {
    
52.                 if(cpx==s[top].x && cpy==s[top].y)
    
53.                 {
    
54.                         printf("%d,%d\n",cpx,cpy);
    
55.                         cpx=s[top].px;cpy=s[top].py;
    
56.                 }
    
57.                 top--;
    
58.         }
    
59.         return 0;
    
60. }
    
61. int main()
    
62. {
    
63.         int i,j;
    
64.         scanf("%d%d",&m,&n);
    
65.         for(i=0;i<=m+1;i++)//初始化，在迷宫的外层要多加一层墙，防出界
    
66.         {
    
67.                 for(j=0;j<=n+1;j++)
    
68.                 {
    
69.                         maze[i][j]=1;
    
70.                         mark[i][j]=0;//所有点都设置未访问
    
71.                 }
    
72.         }
    
73.         for(i=1;i<=m;i++)//输入迷宫
    
74.            for(j=1;j<=n;j++)
    
75.               scanf("%d",&maze[i][j]);
    
76.     seekpath(1,1);//调用
    
77.    
    
78. }

复制代码

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

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

复制代码

有个样例

1. 6 8
   
2. 0 0 1 0 0 0 1 1
   
3. 1 0 0 0 1 0 0 0
   
4. 0 0 0 1 1 0 1 1
   
5. 1 1 0 1 0 0 0 0
   
6. 0 0 0 0 0 1 0 1
   
7. 1 0 1 0 0 0 0 0
   
8. 
   
9. 输出路径：：
   
10. (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谢谢，可以了，太感谢了，虽然栈那段代码还是不太理解

不用谢。