摘要:最近很多同学在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+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号