C++利用遞歸實(shí)現(xiàn)走迷宮

更新時(shí)間：2020年03月20日 06:34:10 作者：春風(fēng)來(lái)不來(lái)

這篇文章主要為大家詳細(xì)介紹了C++利用遞歸實(shí)現(xiàn)走迷宮，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

本文實(shí)例為大家分享了C++利用遞歸實(shí)現(xiàn)走迷宮的具體代碼，供大家參考，具體內(nèi)容如下

要求：

1、將地圖的數(shù)組保存在文件中，從文件中讀取行列數(shù)

2.、動(dòng)態(tài)開(kāi)辟空間保存地圖

3.、運(yùn)行結(jié)束后再地圖上標(biāo)出具體的走法

說(shuō)明：

1、文件中第一行分別放置的是地圖的行數(shù)和列數(shù)

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

3、程序運(yùn)行結(jié)束后用2標(biāo)記走過(guò)的路徑

4、當(dāng)走到“死胡同”時(shí)用3標(biāo)記此路為死路

5、每到一個(gè)點(diǎn)，按照左上右下的順序去試探

6、沒(méi)有處理入口就是"死胡同"的極端情況

maze.h

#ifndef _MAZE_H_
#define _MAZE_H_
#include <fstream> // ifstream
#include <iostream>
#include <cassert>
#include <string>
using namespace std;
 
// 坐標(biāo)類
class Seat
{
public:
 Seat(int _x, int _y)
 :x(_x)
 ,y(_y)
 { }
 int x;
 int y;
};
 
// 迷宮類
 
class Maze
{
private:
 int** _map; // 指向地圖的指針
 int _row; // 存放地圖的行數(shù)
 int _col; // 存放地圖的列數(shù)
public:
 // 構(gòu)造函數(shù) 讀取文件里的地圖 和行數(shù)
 Maze(const string& filePath);
 
private:
 // 判斷是否是路
 bool IsPass(Seat& entry);
 
public:
 // 開(kāi)始走
 bool PassMaze( Seat& entry);
 
 // 打印地圖
 void PrintMap();
 
 // 析構(gòu) 釋放空間
 ~Maze();
};
 
 
#endif

maze.cpp

// 遞歸實(shí)現(xiàn)迷宮
#include "maze.h"
 
// 判斷是否是路
bool Maze::IsPass( Seat& Entry)
{
 if (_map[Entry.x][Entry.y] == 0)
 {
 return true;
 }
 return false;
}
 
// 構(gòu)造函數(shù) 讀取文件里的地圖 和行數(shù)
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;
 }
 
 // 關(guān)閉文件
 read.close();
}
 
// 開(kāi)始走
bool Maze::PassMaze( Seat& Entry)
{
 // 判斷是否走到出口
 if (Entry.x < 0 || Entry.y < 0 || Entry.y >=_row)
 {
 return true;
 }
 
 if (IsPass(Entry))
 {
 // 將走過(guò)的路置為2
 _map[Entry.x][Entry.y] = 2;
 
 // 向左走
 Seat left(Entry.x, Entry.y-1);
 if (PassMaze(left))// 遞歸調(diào)用
 {
 return true;
 }
 
 // 向上走
 Seat up(Entry.x-1, Entry.y);
 if (PassMaze(up)) // 遞歸調(diào)用
 {
 return true;
 }
 
 // 向右走
 Seat right(Entry.x, Entry.y+1);
 if (PassMaze(right)) // 遞歸調(diào)用
 {
 return true;
 }
 
 // 向下走
 Seat down(Entry.x+1, Entry.y);
 if (PassMaze(down))
 {
 return true;
 }
 
 // 走到此處說(shuō)明是死路 置為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;
}

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: