广度搜索问题
今天在书上看到一则例题，走迷宫，输入m行n列构成的迷宫，入口（1,1），出口（m,n）迷宫输入 1表示墙，不可走，0表示通
给出的是伪代码，不全，然后我尝试写出完整代码，但是失败了
/*
mark数组用于标记是否被访问过，已访问标记1，否则标记0
maze数组就是要输入的迷宫
结构体que是搜索中用到的队列，s是一个栈，具体我现在也没明白干什么用
*/
#include<stdio.h>
int mark,maze;
int move={{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,s;
int seekpath(int x,int y)//此函数和上面结构体是书本给出的伪代码
{
int cx,cy,cpx,cpy,dx,dy,i;
que.x=x;que.y=y;
que.px=0;que.py=0;
t++; //起始点进入队列
s.x=x;s.y=y;
s.px=0;s.py=0;
top++; //起始点进入栈
while(h != t)
{
cx=que.x;
cy=que.y; //取队列元素
cpy=que.px;
cpy=que.py;
h++; //出队列
if(cx==m && cy==n)
break;//找到出口
s.x=cx;s.y=cy;//经过结点入栈
s.px=cpx;s.py=cpy;
top++; //经过位置入栈
for(i=0;i<4;i++)//对4个方向进行试探
{
dx=cx+move;//计算新结点位置
dy=cy+move;
if(maze==0 && mark==0)
{ //如果可以走
mark=1;//标记此位置
que.x=dx;que.y=dy;
que.px=cx;que.py=cy;
t++; //进入队列
}
}
}//以下代码就看不懂了，不知道是不是输出，但是不行
printf("%d,%d\n",cx,cy);
while(top != 0) //书上说是查找走过的路径
{
if(cpx==s.x && cpy==s.y)
{
printf("%d,%d\n",cpx,cpy);
cpx=s.px;cpy=s.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=1;
mark=0;//所有点都设置未访问
}
}
for(i=1;i<=m;i++)//输入迷宫
for(j=1;j<=n;j++)
scanf("%d",&maze);
seekpath(1,1);//调用
}
主要是对伪代码中 这段不理解，感觉不像是输出
printf("%d,%d\n",cx,cy);
while(top != 0) //书上说是查找走过的路径
{
if(cpx==s.x && cpy==s.y)
{
printf("%d,%d\n",cpx,cpy);
cpx=s.px;cpy=s.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)
第28行，cpy改为cpx 50行到58行之间的代码是将保存在栈s里的路径打印出来 50行到58行之间的代码是将保存在栈s里的路径打印出来 在23行和24行之间加mark=1;，将起始位置标记为已访问 ko12 发表于 2016-1-29 12:38
在23行和24行之间加mark=1;，将起始位置标记为已访问
O(∩_∩)O谢谢，可以了，太感谢了，虽然栈那段代码还是不太理解 独一无② 发表于 2016-1-29 13:50
O(∩_∩)O谢谢，可以了，太感谢了，虽然栈那段代码还是不太理解
不用谢。{:5_109:}
页:
[1]