c++实现的深度优先遍历迷宫,迷宫大小为20*20,代码简练清楚,内涵关键注释。代码与网上都不一样。
深度优先遍历迷宫,核心思想是借助一个栈,站在一个节点上时,将它附近可以走的节点存在栈中,再按顺序找到下一个节点,重复刚才的操作,直到找到最终的终点。
实现细节:
- Stack函数不需要多说了,自己定义一个栈,这个栈是很关键的,像我刚才说的,他用来记录去过的节点,以保证不重不漏
- 重点是slove函数,slove()原理:
递归出口为找到出口或者没有出口的条件下整个地图被全部遍历将入口读出;分别进行上下左右移动并判定是否可走;如果可走则将其压栈,并递归;否则返回上一步。这是一个递归函数,因此深度优先本身的效率不高。
对于一个节点,坐标(x,y),我们这里规定只允许向四个方向移动,所以需要找的坐标是(x-1,y),(x+1,y)(x,y-1),(x,y+1),分别判断是否可以去,且是否去过,这就是本项目中最重要的地方了!
void slove(zuobiao c,Stack &a,int (*Map)[20]){
zuobiao l=a.ntop();
if(l.x==c.x&&l.y==c.y){
return ;
}
if(pass(l.x,l.y+1,Map)){
zuobiao m;
m.x=l.x;m.y=l.y+1;
vi[m.x][m.y]=1;
a.push(m);
slove(c,a,Map);
}
else if(pass(l.x,l.y-1,Map)){
zuobiao m;
m.x=l.x;m.y=l.y-1;
vi[m.x][m.y]=1;
a.push(m);
slove(c,a,Map);
}
else if(pass(l.x-1,l.y,Map)){
zuobiao m;
m.x=l.x-1;m.y=l.y;
vi[m.x][m.y]=1;
a.push(m);
slove(c,a,Map);
}
else if(pass(l.x+1,l.y,Map)){
zuobiao m;
m.x=l.x+1;m.y=l.y;
vi[m.x][m.y]=1;
a.push(m);
slove(c,a,Map);
}
else {
if(a.bout()){
slove(c,a,Map);
}
else {
cout<<"没有路径可以到达指定的地点";
}
}
}