这期内容当中小编将会给大家带来有关怎么在C++中利用递归走迷宫,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。
1、文件中第一行分别放置的是地图的行数和列数
2、其中1表示墙,即路不通,0表示路,即通路
3、程序运行结束后用2标记走过的路径
4、当走到“死胡同”时用3标记此路为死路
5、每到一个点,按照 左 上 右 下 的顺序去试探
6、没有处理入口就是"死胡同"的极端情况
maze.h
#ifndef _MAZE_H_
#define _MAZE_H_
#include <fstream> // ifstream
#include <iostream>
#include <cassert>
#include <string>
using namespace std;
// 坐标类
class Seat
{
public:
Seat(int _x, int _y)
:x(_x)
,y(_y)
{ }
int x;
int y;
};
// 迷宫类
class Maze
{
private:
int** _map; // 指向地图的指针
int _row; // 存放地图的行数
int _col; // 存放地图的列数
public:
// 构造函数 读取文件里的地图 和行数
Maze(const string& filePath);
private:
// 判断是否是路
bool IsPass(Seat& entry);
public:
// 开始走
bool PassMaze( Seat& entry);
// 打印地图
void PrintMap();
// 析构 释放空间
~Maze();
};
#endif
maze.cpp
// 递归实现迷宫
#include "maze.h"
// 判断是否是路
bool Maze::IsPass( Seat& Entry)
{
if (_map[Entry.x][Entry.y] == 0)
{
return true;
}
return false;
}
// 构造函数 读取文件里的地图 和行数
Maze::Maze(const string& filePath )
{
ifstream read(filePath);
string str_row_col, str_temp;
// 读取第一行
getline(read, str_row_col);
// 获取行
str_temp = str_row_col.substr(0, str_row_col.find_first_of(','));
_row = atoi(str_temp.c_str());
// 获取列
str_temp = str_row_col.substr( str_row_col.find_first_of(',')+1);
_col = atoi(str_temp.c_str());
// 为地图分配空间
_map = new int*[_row];
for (int index = 0; index < _col; ++index)
{
_map[index] = new int[_col];
}
int index_col = 0;
int index_row = 0;
// 填充地图
while (!read.eof())
{
// 获取一行
getline(read, str_temp);
char * line = (char*)str_temp.c_str();
while ((*line) != '\0')
{
if (*line == '0' || *line == '1')
{
_map[index_row][index_col++] = *line - '0';
}
++line;
}
++index_row;
index_col = 0;
}
// 关闭文件
read.close();
}
// 开始走
bool Maze::PassMaze( Seat& Entry)
{
// 判断是否走到出口
if (Entry.x < 0 || Entry.y < 0 || Entry.y >=_row)
{
return true;
}
if (IsPass(Entry))
{
// 将走过的路置为2
_map[Entry.x][Entry.y] = 2;
// 向左走
Seat left(Entry.x, Entry.y-1);
if (PassMaze(left))// 递归调用
{
return true;
}
// 向上走
Seat up(Entry.x-1, Entry.y);
if (PassMaze(up)) // 递归调用
{
return true;
}
// 向右走
Seat right(Entry.x, Entry.y+1);
if (PassMaze(right)) // 递归调用
{
return true;
}
// 向下走
Seat down(Entry.x+1, Entry.y);
if (PassMaze(down))
{
return true;
}
// 走到此处说明是死路 置为3
_map[Entry.x][Entry.y] = 3;
}
return false;
}
// 打印地图
void Maze::PrintMap()
{
for (int row = 0; row<_row; ++row)
{
for (int col = 0; col<_col; ++col)
{
cout << _map[row][col] << " ";
}
cout <<endl;
}
cout <<endl;
}
// 释放空间
Maze::~Maze()
{
for (int idx = 0; idx < _row; ++idx )
{
delete[] _map[idx];
}
delete[] _map;
_map = NULL;
}
上述就是小编为大家分享的怎么在C++中利用递归走迷宫了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注亿速云行业资讯频道。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。