在学习“数据结构”一书的时候看到这一道题, 为了展示栈的用法对迷宫做了以下限制
1.迷宫的四周都是不可通的,这样就避免解决边界问题
2.从(1,1)出发,终点为(8,8), 这里用10*10的迷宫为例子
走迷宫通常用的穷举法,即从入口出发,沿着某一方向向前探索,如果能走通就继续向前走,如果不能就原路返回换一个方向再继续探索,直到找到重点或者终止探索。为了能回到原来的位置,比较理想的是用栈来实现,把探索过的位置压栈,当走到不能再走的路径的时候,退回原路换方向继续探索。
如果当前位置是可通的就将其压栈,并把当前位置指向下一个位置。 如果当前位置不可通,就顺着来的方向退到前一个位置,然后沿其他方向探索,如果前一个位置的所有方向都探索了,就继续往回走,重复上面的过程。默认探索方向是向右开始探索,沿逆时针方向变换探索方向。
算法可以简单的用下面的语言描述:
设定当前位置的初始值为入口位置
do{
若当前位置可通,
则{
把当前位置压栈;
如果当前位置是出口位置,结束程序;
否则把当前位置设置为其右边的位置
}
否者{
若栈不空且四周均不通{
删除栈顶位置,直到找到一个相邻位置可以通的位置
}
若栈不空且栈顶位置周围还有没有探索过的方向,
则设定当前位置为下一个没有探索过的位置
}
}while(栈不空)
1 #include<iostream>
2 #include<stack>
3 #include<string>
4 using namespace std;
5 /*
6 function: find a path in maze
7 authour: Lai XingYu
8 date: 2018/05/10
9 */
10 bool vis[11][11];//储存每个位置的访问情况,false 为没有访问, true表示访问过
11
12 class point{
13 public:
14 int x;
15 int y;
16 int dir;
17 point(int a, int b,int d=1){
18 x = a;
19 y = b;
20 dir = d;
21 }
22 bool equal(point a){return x==a.x && y==a.y;}
23
24 };
25 //每个位置未访问过,并且是可以通过的 则该位置是“可通”的
26 bool pass(int maze[][10], point pos){
27 return !vis[pos.x][pos.y] && !maze[pos.x][pos.y];
28 }
29 //顺时针找下一个未探索的位置
30 point next_position(point a, int dir){
31 if(dir==1) return point(a.x+1, a.y);
32 if(dir==2) return point(a.x, a.y+1);
33 if(dir==3) return point(a.x-1, a.y);
34 if(dir==4) return point(a.x, a.y-1);
35 }
36
37 stack<point> maze_path(int maze[][10], point start, point end){
38 stack<point> path;
39 point current_position = start;
40 do{
41 if(pass(maze, current_position)){
42 vis[current_position.x][current_position.y] = true;//标记已访问过的位置
43 point temp(current_position.x, current_position.y, 1);
44 path.push(temp);
45 if(current_position.equal(end)) return path;
46 current_position = next_position(current_position, 1);
47 }else{
48 point temp = path.top();
49 path.pop();//四个方向都探索过的位置,继续往回走
50 while(temp.dir==4 && !path.empty()){
51 temp = path.top();
52 path.pop();
53 }
54 if(temp.dir<4){
55 temp.dir++;
56 path.push(temp);
57 current_position = next_position(temp, temp.dir);
58 }
59 }
60 }while(path.size());
61 return path;
62 }
63
64 int main(){//1表示该位置不能通过, 反之可以通过
65 int maze[][10]={{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},
66 {1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}};
67 point start(1,1), end(8,8);
68 stack<point> path = maze_path(maze, start, end);
69 while(path.size()) {
70 printf("(%d,%d) ", path.top().x, path.top().y);
71 path.pop();
72 }
73 return 0;}
原文链接: https://www.cnblogs.com/mr-stn/p/9022142.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/273665
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!