第9节 迷宫求解
时间：2010-09-02 来源：chinazhangjie
1 /* 主题: 迷宫求解（使用栈）
2 * 作者: chinazhangjie(邮箱:[email protected])
3 * 开发语言: C++
4 * 开发环境: Microsoft Visual Studio 2008
5 * 日期: 2010.09.02
6 * 备注:（1）测试量不够，总感觉计算路径有一些问题。
7 * （2）请用vector代替stack，stack在调试程序时极其不方便，
8 或者你可以继承vector写一个方便使用的stack。
9 */
10 #include <vector> // for STL vector
11 #include <stack> // for STL stack
12 #include <iostream>
13 using std::vector;
14 using std::stack;
15 using std::cout;
16 using std::endl;
17
18 struct point {
19 int x ;
20 int y ;
21 point() {}
22 point(int nx,int ny) : x(nx),y(ny) {}
23 bool operator == (const point& p) {
24 return p.x == x && p.y == y;
25 }
26 };
27 struct selem_type {
28 int ord; // 通道块在路径上的“序号”
29 point seat; // 通道块在迷宫中的“坐标位置”
30 int di; // 从此通道块走向下一通道块的方向
31 selem_type() {}
32 selem_type(int nord,point pseat,int ndi)
33 :ord(nord),seat(pseat),di(ndi)
34 {}
35 };
36 class maze {
37 public:
38 // 构造函数
39 maze(const vector<vector<bool> >& rmap,int nw,int nh)
40 :width(nw),height(nh) {
41 vector<vector<bool> >::const_iterator ite = rmap.begin();
42 for (; ite != rmap.end(); ++ ite) {
43 map.push_back((*ite));
44 }
45 }
46 // 拷贝构造函数
47 maze(const maze& m) {
48 map = m.map;
49 width = m.get_width();
50 height = m.get_width();
51 }
52
53 // 返回迷宫宽度
54 int get_width() const { return width; }
55 // 返回迷宫高度
56 int get_heigth() const { return height; }
57
58 // 打印路径
59 void print_path() {
60 if (!__get_path())
61 return ;
62 vector<selem_type> tmp_v;
63 stack<selem_type> tmp = path;
64 for (int i = 0; i < path.size() ; ++ i) {
65 selem_type e = tmp.top();
66 tmp_v.push_back(e);
67 tmp.pop();
68 }
69 for (int i=tmp_v.size()-1; i >= 0; -- i) {
70 cout <<'['
71 << tmp_v[i].seat.x << ','
72 << tmp_v[i].seat.y << ']'
73 << " -> ";
74 }
75 cout << '[' << tmp_v[0].seat.x << ','
76 << tmp_v[0].seat.y << ']'
77 << "(exit)" << endl;
78 }
79
80 // 打印迷宫
81 void print_maze() {
82
83 vector<vector<bool> >::iterator ite1 = map.begin();
84 vector<bool>::iterator ite2;
85 for (; ite1 != map.end(); ++ ite1) {
86 ite2 = (*ite1).begin();
87 for (;ite2 != (*ite1).end(); ++ ite2) {
88 cout << *ite2 << ' ';
89 }
90 cout << endl;
91 }
92 }
93
94 // 重载赋值运算符
95 maze& operator = (const maze& rhs) {
96 if (this == &rhs)
97 return *this;
98 map = rhs.map;
99 width = rhs.get_width();
100 height = rhs.get_heigth();
101 return *this;
102 }
103
104 private:
105 // 清空栈
106 void __clear_stack() {
107 int len = path.size();
108 for (int i=0; i < len; ++ i)
109 path.pop();
110 }
111
112 // 计算路径
113 bool __get_path() {
114 __clear_stack();
115 // 设定出口
116 point exit;
117 exit.x = height-2;
118 exit.y = width-2;
119
120 // 记录足迹
121 vector<vector<bool> > foot;
122 for (int i =0; i < height; ++ i)
123 foot.push_back(vector<bool>(width,false));
124
125 // 设定当前位置为入口位置
126 point curpos(1,1);
127 int curstep = 1; // 探索第一步
128 do {
129 // 当前位置可以通过，即是未曾走到过的通道块
130 if (map[curpos.x][curpos.y] && !foot[curpos.x][curpos.y]) {
131 // 留下足迹
132 foot[curpos.x][curpos.y] = true;
133 path.push(selem_type(curstep,curpos,1)); // 加入路径
134 if (curpos == exit)
135 return true; // 到达终点（出口）
136 // 下一个位置是当前位置的东邻
137 curpos.y += 1;
138 ++ curstep; // 探索下一步
139 }
140 else { // 当前位置不能通过
141 if (!path.empty()) {
142 selem_type e = path.top();
143 path.pop();
144 while (e.di == 4 && !path.empty()) {
145 foot[e.seat.x][e.seat.y] = true;
146 e = path.top();
147 path.pop();
148 }
149 if (e.di < 4) {
150 ++ e.di;
151 path.push(e);
152 if (e.di == 2) {
153 curpos.x = e.seat.x;
154 curpos.y = e.seat.y + 1;
155 }
156 if (e.di == 3) {
157 curpos.x = e.seat.x + 1;
158 curpos.y = e.seat.y;
159 }
160 if (e.di == 4) {
161 curpos.x = e.seat.x - 1;
162 curpos.y = e.seat.y;
163 }
164 }
165 }
166 }
167 } while (!path.empty());
168 return false;
169 }
170
171 private:
172 vector<vector<bool> > map; // 迷宫地图（1，通。0，阻）
173 stack<selem_type> path; // 路径
174 int width; // 宽度
175 int height; // 高度
176 };
相关阅读 更多 +
