C++语言利用递归实现走迷宫
Vivian 2018-06-19 来源 : 阅读 1849 评论 0

摘要:最近很多同学在C++语言程序设计面试时都遇到这样一个问题,如何运用C++语言实现走迷宫,针对这个问题,小编这里找到一种实现方法,就是利用递归实现走迷宫。本文介绍了利用C++语言程序设计中的递归实现走迷宫的方法,具体如下,希望对大家学习C++语言有所帮助。

最近很多同学在C++语言程序设计面试时都遇到这样一个问题,如何运用C++语言实现走迷宫,针对这个问题,小编这里找到一种实现方法,就是利用递归实现走迷宫。本文介绍了利用C++语言程序设计中的递归实现走迷宫的方法,具体如下

要求:

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

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

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

 

说明:

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

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

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

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

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

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

maze.h

 

[cpp] view plain copy print?

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

 

maze.cpp

[cpp] view plain copy print?
1. // 递归实现迷宫  
2. #include "maze.h"  
3.   
4. // 判断是否是路  
5. bool Maze::IsPass( Seat& Entry)  
6. {  
7.     if (_map[Entry.x][Entry.y] == 0)  
8.     {  
9.         return true;  
10.     }  
11.     return false;  
12. }  
13.   
14. // 构造函数 读取文件里的地图 和行数  
15. Maze::Maze(const string& filePath )  
16. {  
17.     ifstream read(filePath);  
18.     string str_row_col, str_temp;  
19.     // 读取第一行  
20.     getline(read, str_row_col);  
21.     // 获取行  
22.     str_temp = str_row_col.substr(0, str_row_col.find_first_of(','));  
23.     _row = atoi(str_temp.c_str());  
24.     // 获取列  
25.     str_temp = str_row_col.substr( str_row_col.find_first_of(',')+1);  
26.     _col = atoi(str_temp.c_str());  
27.   
28.     // 为地图分配空间  
29.     _map = new int*[_row];  
30.     for (int index = 0; index < _col; ++index)  
31.     {  
32.         _map[index] = new int[_col];  
33.     }  
34.   
35.     int index_col = 0;  
36.     int index_row = 0;  
37.     // 填充地图  
38.     while (!read.eof())  
39.     {  
40.         // 获取一行  
41.         getline(read, str_temp);  
42.         char * line = (char*)str_temp.c_str();  
43.         while ((*line) != '\0')  
44.         {  
45.             if (*line == '0' || *line == '1')  
46.             {  
47.                 _map[index_row][index_col++] = *line - '0';  
48.             }  
49.             ++line;  
50.         }  
51.         ++index_row;  
52.         index_col = 0;  
53.     }  
54.   
55.     // 关闭文件  
56.     read.close();  
57. }  
58.   
59. // 开始走  
60. bool Maze::PassMaze( Seat& Entry)  
61. {  
62.     // 判断是否走到出口  
63.     if (Entry.x < 0 || Entry.y < 0 || Entry.y >=_row)  
64.     {  
65.         return true;  
66.     }  
67.   
68.     if (IsPass(Entry))  
69.     {  
70.         // 将走过的路置为2  
71.         _map[Entry.x][Entry.y] = 2;  
72.   
73.         // 向左走  
74.         Seat left(Entry.x, Entry.y-1);  
75.         if (PassMaze(left))// 递归调用  
76.         {  
77.             return true;  
78.         }  
79.   
80.         // 向上走  
81.         Seat up(Entry.x-1, Entry.y);  
82.         if (PassMaze(up)) // 递归调用  
83.         {  
84.             return true;  
85.         }  
86.   
87.         // 向右走  
88.         Seat right(Entry.x, Entry.y+1);  
89.         if (PassMaze(right)) // 递归调用  
90.         {  
91.             return true;  
92.         }  
93.   
94.         // 向下走  
95.         Seat down(Entry.x+1, Entry.y);  
96.         if (PassMaze(down))  
97.         {  
98.             return true;  
99.         }  
100.   
101.         // 走到此处说明是死路 置为3  
102.         _map[Entry.x][Entry.y] = 3;  
103.   
104.     }  
105.       
106.     return false;  
107. }  
108.   
109. // 打印地图  
110. void Maze::PrintMap()  
111. {  
112.     for (int row = 0; row<_row; ++row)  
113.     {  
114.         for (int col = 0; col<_col; ++col)  
115.         {  
116.             cout << _map[row][col] << " ";  
117.         }  
118.         cout <<endl;  
119.     }  
120.     cout <<endl;  
121. }  
122.   
123. // 释放空间  
124. Maze::~Maze()  
125. {  
126.     for (int idx = 0; idx < _row; ++idx  )  
127.     {  
128.         delete[] _map[idx];  
129.     }  
130.     delete[] _map;  
131.     _map = NULL;  
132. }

以上就是利用C++语言程序设计中的递归实现走迷宫的方法,希望对C/C+有兴趣的朋友有所帮助。了解更多内容,请关注职坐标编程语言C/C+频道!

本文由 @Vivian 发布于职坐标。未经许可,禁止转载。
喜欢 | 0 不喜欢 | 2
看完这篇文章有何感觉?已经有2人表态,0%的人喜欢 快给朋友分享吧~
评论(0)
后参与评论

您输入的评论内容中包含违禁敏感词

我知道了

助您圆梦职场 匹配合适岗位
验证码手机号,获得海同独家IT培训资料
选择就业方向:
人工智能物联网
大数据开发/分析
人工智能Python
Java全栈开发
WEB前端+H5

请输入正确的手机号码

请输入正确的验证码

获取验证码

您今天的短信下发次数太多了,明天再试试吧!

提交

我们会在第一时间安排职业规划师联系您!

您也可以联系我们的职业规划师咨询:

小职老师的微信号:z_zhizuobiao
小职老师的微信号:z_zhizuobiao

版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
 沪公网安备 31011502005948号    

©2015 www.zhizuobiao.com All Rights Reserved

208小时内训课程