C++语言利用循环和栈实现走迷宫-职坐标

C++语言利用循环和栈实现走迷宫

Vivian 2018-06-19 来源：阅读 1323 评论 0

摘要：本文主要向大家介绍了C++语言利用循环和栈实现走迷宫，通过具体的代码向大家展示，希望对大家学习C++语言有所帮助。

本文主要向大家介绍了C++语言利用循环和栈实现走迷宫，通过具体的代码向大家展示，希望对大家学习C++语言有所帮助。

要求：

1、将地图的数组保存在文件中，从文件中读取行列数

2.、动态开辟空间保存地图

3.、运行结束后再地图上标出具体的走法

说明：

1、文件中第一行分别放置的是地图的行数和列数

2、其中1表示墙，即路不通，0表示路，即通路

3、程序运行结束后用2标记走过的路径

4、当走到“死胡同”时用3标记此路为死路

5、每到一个点，按照左上右下的顺序去试探

6、没有处理入口就是"死胡同"的极端情况

地图文件截图：

C++语言利用循环和栈实现走迷宫

代码示例：maze.h

[cpp] view plain copy print?
1. #ifndef _MAZE_H_  
2. #define  _MAZE_H_  
3.   
4. #include <stack>        
5. #include <fstream>    // ifstream  
6. #include <iostream>  
7. #include <string>  
8. using namespace std;  
9.   
10. // 坐标类  
11. class Seat  
12. {  
13. public:  
14.     Seat(int _x, int _y)  
15.         :x(_x)  
16.         ,y(_y)  
17.     {   }  
18.     int x;  
19.     int y;  
20. };  
21.   
22. // 迷宫类  
23.   
24. class Maze  
25. {  
26. private:  
27.     int** _map; // 指向地图的指针  
28.     int _row; // 存放地图的行数  
29.     int _col; // 存放地图的列数  
30. public:  
31.     // 构造函数  读取文件里的地图 和行数  
32.     Maze(const string& filePath);  
33.   
34. private:  
35.     // 判断是否是路  
36.     bool IsPass(Seat& entry);  
37.   
38. public:  
39.     // 开始走  
40.     bool PassMaze(stack<Seat>& s, Seat& entry);  
41.   
42.     // 打印地图  
43.     void PrintMap();  
44.   
45.     // 析构 释放空间  
46.     ~Maze();  
47. };  
48. #endif

maze.cpp

[cpp] view plain copy print?
1. //  迷宫之递归实现  
2. #include "maze.h"  
3.   
4. // 构造函数  
5. Maze::Maze(const string& filePath)  
6. {  
7.     ifstream mapFile(filePath, ofstream::out);  
8.     assert(mapFile); // 断言文件是否存在  
9.     string str_row_col; //第一行  获取行和列  
10.     string str_temp;  // 临时字符串   
11.   
12.     // 获取行列的个数  
13.     getline(mapFile,str_row_col);// 读取第一行  
14.     str_temp = str_row_col.substr(0,  str_row_col.find_first_of(','));// 取得字符串中的字串获取行数  
15.     _row = atoi(str_temp.c_str()); // atoi将字符串转为数字  
16.     str_temp = str_row_col.substr(str_row_col.find_first_of(',')+1); // 取得字符串中的列数  
17.     _col = atoi(str_temp.c_str()); // atoi将字符串转为数字  
18.   
19.     // 分配空间  
20.     _map = new int*[_row];    
21.     for (int idx = 0; idx < _col; ++idx)  
22.     {  
23.         _map[idx] = new int[_col];  
24.     }  
25.       
26.   
27.     // 填充地图  
28.     int index_row = 0; // 放置地图 二维数组的行索引  
29.     int index_col = 0; // 放置地图 二维数组的列索引  
30.     while (!mapFile.eof())  
31.     {  
32.         getline(mapFile, str_temp);  
33.         char* a_line = (char*)str_temp.c_str();  
34.         // 遍历一行  
35.         while (*a_line != '\0')  
36.         {  
37.             if (*a_line == '0' || *a_line == '1')  
38.             {  
39.                 _map[index_row][index_col++] = *a_line - '0'; // 减0  是将字符'0'的 ASCII对应的十进制值减去  
40.             }  
41.             a_line++; // 向后移动指针  
42.         }  
43.         ++index_row;  
44.         index_col = 0; // 每处理完一行后将列索引置0  
45.     }  
46.     mapFile.close();  
47. }  
48.   
49.     // 判断是否是路  
50. bool Maze::IsPass(Seat& entry)  
51. {  
52.     if (entry.x < 0 || entry.y < 0 || entry.y >= _col || entry.x >= _row)  
53.     {  
54.         return true;  
55.     }  
56.     if (_map[entry.x][entry.y] == 0)  
57.     {  
58.         return true;  
59.     }  
60.     return false;  
61. }  
62.   
63.   
64. // 开始走  
65. void Maze::PassMaze( Seat& entry)  
66. {  
67.     stack<Seat> s;  
68.     if (IsPass(entry))  
69.     {  
70.         s.push(entry); // 压栈当前位置  
71.         while (!s.empty())  // 栈不为空继续  
72.         {  
73.             Seat curSeat = s.top(); // 取得栈顶存储的位置  
74.             // 走到边界  
75.             if (curSeat.x < 0 || curSeat.y < 0 || entry.y >= _col || entry.x >= _row )  
76.             {  
77.                 return;  
78.             }  
79.             _map[curSeat.x][curSeat.y] = 2;  // 将走过的路标记为2  
80.   
81.             // 往左走  
82.             Seat left(curSeat.x, curSeat.y-1);  
83.             if (IsPass(left))  
84.             {  
85.                 s.push(left);   
86.                 continue;  
87.             }  
88.             // 往上走  
89.             Seat up(curSeat.x-1, curSeat.y);  
90.             if (IsPass(up))  
91.             {  
92.                 s.push(up);  
93.                 continue;  
94.             }  
95.             // 往右走  
96.             Seat right(curSeat.x, curSeat.y+1);  
97.             if (IsPass(right))  
98.             {  
99.                 s.push(right);  
100.                 continue;  
101.             }  
102.             // 往下走  
103.             Seat down(curSeat.x+1, curSeat.y);  
104.             if (IsPass(down))  
105.             {  
106.                 s.push(down);  
107.                 continue;  
108.             }  
109.   
110.             // 运行到此处说明 每个方向都没有路可走 是死路标记为3  
111.             _map[curSeat.x][curSeat.y] = 3;  
112.             // 出栈这个“死路位置”  
113.             s.pop();  
114.         }  
115.     }  
116. }  
117.   
118. // 打印地图  
119. void Maze::PrintMap()  
120. {  
121.     for (int index_row = 0; index_row < _row; ++index_row)  
122.     {  
123.         for (int index_col = 0; index_col < _col; ++index_col)  
124.         {  
125.             cout << _map[index_row][index_col] <<" ";  
126.         }  
127.         cout <<endl;  
128.     }  
129.     cout <<endl;  
130. }  
131.   
132. // 析构  
133. Maze::~Maze()  
134. {  
135.     for (int idx = 0; idx < _row; ++idx  )  
136.     {  
137.         delete[] _map[idx];  
138.     }  
139.     delete[] _map;  
140.     _map = NULL;  
141. }

test.cpp

[cpp] view plain copy print?
1. int main()  
2. {  
3.     Maze m1("map.txt"); // 构造一个迷宫对象  
4.     m1.PrintMap();   // 走之前打印  
5.     m1.PassMaze(Seat(9, 4));  //开始走  传递迷宫入口点  
6.     m1.PrintMap(); // 结束后再次打印  
7.     return 0;  
8. }

截图“：

C++语言利用循环和栈实现走迷宫