C++實(shí)現(xiàn)迷宮生成與解決
更新時(shí)間：2020年12月21日 17:33:09 作者：J__M__C
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)迷宮生成與解決，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課要求解決一個(gè)迷宮問題，這里給定長(zhǎng)寬用prime算法隨機(jī)生成了一個(gè)迷宮并從指定起點(diǎn)與終點(diǎn)打印出了迷宮的解決方案，此處用到了棧數(shù)據(jù)結(jié)構(gòu)，這里的jmc::Stack是我自己寫的棧，這里就不放了，可以換成一切具有常規(guī)意義的empty、pop、push接口的棧ADT，或者直接使用std::stack就行，注意頭文件的#include"Stack"也改一下
Maze.h:
#pragma once
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<random>
#include<string>
#include"Stack.h"
#include<functional>
#include<algorithm>
#include<cassert>
namespace jmc {
using blockpic = std::vector<std::string>;
const blockpic block{
"▉"," ","※"
};
class locat {
public:
using rowType = size_t;
using calType = size_t;
locat(rowType r = 0, calType c = 0)
:loc(r, c) {}
rowType x(void)const { return loc.first; } //返回一維坐標(biāo)
rowType x(const rowType& r) { loc.first = r; return loc.first; }//修改并返回一維坐標(biāo)
calType y(void)const { return loc.second; } //返回二維坐標(biāo)
calType y(const calType& c) { loc.second = c; return loc.second; }//修改并返回二維坐標(biāo)
locat up(void)const { return { loc.first - 1, loc.second }; }
locat down(void)const { return { loc.first + 1, loc.second }; }
locat left(void)const { return { loc.first, loc.second - 1 }; }
locat right(void)const { return { loc.first, loc.second + 1 }; }
locat& operator()(const rowType& r, const calType& c) {
x(r), y(c);
return *this;
}
locat& operator()(const locat& oth) {
return (*this)(oth.x(), oth.y());
}
bool operator<(const locat& oth)const {
return x() == oth.x() ? y() < oth.y() : x() < oth.x();
}
bool operator==(const locat& oth)const {
return x() == oth.x() && y() == oth.y();
}
friend std::ostream& operator<<(std::ostream& o, const locat& l)
{
o << '(' << l.x() << ',' << l.y() << ')';
return o;
}
private:
std::pair<rowType, calType> loc;
};
class Maze
{
public:
using rowType = locat::rowType;
using calType = locat::calType;
using locats = std::vector<locat>;
enum blockType {
wall,
road,
way
};
Maze(const locat& l) :xyMsg(l), Map(l.x(), mazeLine(l.y(), wall)) {}
Maze(rowType row, calType cal); // 隨機(jī)生成一個(gè)迷宮，采用Prim算法
std::function<locat(const locat& l)> operat[4]{
[](const locat& l) {return l.up(); },
[](const locat& l) {return l.down(); },
[](const locat& l) {return l.left(); },
[](const locat& l) {return l.right(); },
};
auto& operator()(const rowType& r,const calType& c) {
return Map[r][c];
}
auto& operator()(const locat& p) {
return (*this)(p.x(), p.y());
}
rowType row(void) { return xyMsg.x(); } // 返回迷宮的行數(shù)
calType cal(void) { return xyMsg.y(); } // 返回迷宮的列數(shù)
locat& start(void) { return _start; }
locat& end(void) { return _end; }
void show(const blockpic pic = block); // 打印迷宮
private:
using mazeLine = std::vector<blockType>; // 單行迷宮
using mazeMap = std::vector<mazeLine>; // 迷宮圖
locats findWall(const locat& p); //返回一個(gè)路周圍的墻
locats findRoad(const locat& p); //返回一個(gè)墻周圍的路
locat xyMsg;
mazeMap Map;
locat _start, _end;
};
//給出迷宮問題的解決方案
class Solute
:public Maze
{
public:
Solute(const rowType& r, const calType& c)
:Maze(r, c) {
rowType tmpR;
calType tmpC;
show();
std::cout << std::endl << std::endl
<< "請(qǐng)輸入起點(diǎn)的行坐標(biāo)與列坐標(biāo):";
std::cin >> tmpR >> tmpC;
(*this)(end()(tmpR, tmpC)) = way;
std::cout << "請(qǐng)輸入終點(diǎn)的行坐標(biāo)與列坐標(biāo):";
std::cin >> tmpR >> tmpC;
(*this)(start()(tmpR, tmpC)) = way;
solve(start());
show();
std::cout << std::endl << std::endl;
showWay();
}
bool isIn(const locat& p) {
return p.x() < row() && p.y() < cal();
}
bool solve(const locat& p);
void showWay(void) {
if (!ans.empty()) {
std::cout << ans.top();
ans.pop();
if (!ans.empty())
std::cout << " -> ";
showWay();
}
};
private:
Maze mark{ locat{row(),cal()} };
jmc::Stack<locat> ans{};
};
}
Maze.cpp:
#include "Maze.h"
jmc::Maze::Maze(rowType row, calType cal)
:xyMsg(2 * row + 1, 2 * cal + 1), Map(2 * row + 1, mazeLine(2 * cal + 1, wall))
{
// 初始化隨機(jī)數(shù)生成器
static std::random_device rd;
static std::default_random_engine e(rd());
static std::uniform_int_distribution<> d;
std::map<blockType, std::set<locat>> mark{
{wall,{}},{road,{}}
};
for (rowType i = 1; i < row * 2 + 1; i += 2)
{
for (calType j = 1; j < cal * 2 + 1; j += 2)
{
(*this)(i,j) = road;
}
}
//隨機(jī)生成起點(diǎn)，把邊框分為四段
auto i = d(e, decltype(d)::param_type{ 0,3 });
auto j = i % 2 ?
d(e, decltype(d)::param_type{ 0,(int)row - 2 }) :
d(e, decltype(d)::param_type{ 0,(int)cal - 2 });
switch (i)
{
case 0:
_start(j, 0); break;
case 1:
_start(0, j - 1); break;
case 2:
_start(row - 1, j); break;
case 3:
_start(j + 1, cal - 1); break;
}
_start(_start.x() * 2 + 1, _start.y() * 2 + 1); //將起點(diǎn)對(duì)應(yīng)到實(shí)際位置
locats tmpRoad{ _start };
locats tmpWall = findWall(_start);
mark[road].insert(tmpRoad.begin(), tmpRoad.end());
mark[wall].insert(tmpWall.begin(), tmpWall.end());
while (!mark[wall].empty())
{
auto it = mark[wall].begin();
std::advance(it,
d(e, decltype(d)::param_type{ 0,(int)mark[wall].size()-1 }));
tmpRoad = findRoad(*it); //隨機(jī)將一個(gè)wall集合中的元素傳入findRoad
auto s1 = mark[road].size(); //插入set前set大小
bool flag = false;
for (auto& i : tmpRoad)
{
mark[road].insert(i);
if (s1 != mark[road].size()) {
s1 = mark[road].size();
tmpWall = findWall(i);
mark[wall].insert(tmpWall.begin(), tmpWall.end());
flag = true;
}
}
//若size有變化，表示此wall周圍的road有未標(biāo)記的，將此wall置為road
if (flag) {
mark[road].insert(*it);
(*this)(*it) = road;
}
mark[wall].erase(it);
}
_end(tmpRoad.back());
}
void jmc::Maze::show(const blockpic pic)
{
size_t m{}, n{};
for (const auto& i : Map)
{
for (const auto& j : i)
{
std::cout << pic[j];
}
std::cout << m++ << std::endl;
}
for (size_t i = 0; i < cal(); printf("%2d", i++));
}
jmc::Maze::locats jmc::Maze::findWall(const locat& p)
{
locats ret;
locat tmp;
if (p.x() != 1) {
tmp = p.up();
if ((*this)(tmp) == wall)
ret.push_back(tmp);
}
if (p.y() != 1) {
tmp = p.left();
if ((*this)(tmp) == wall)
ret.push_back(tmp);
}
if (p.x() != row() - 2) {
tmp = p.down();
if ((*this)(tmp) == wall)
ret.push_back(tmp);
}
if (p.y() != cal() - 2) {
tmp = p.right();
if ((*this)(tmp) == wall)
ret.push_back(tmp);
}
return ret;
}
jmc::Maze::locats jmc::Maze::findRoad(const locat& p)
{
assert(p.x() != 0 && p.x() != row() && p.y() != 0 && p.y() != cal());
locats ret;
locat tmp;
for (auto& i : operat)
{
tmp = i(p);
if ((*this)(tmp) == road)
ret.push_back(tmp);
}
return ret;
}
bool jmc::Solute::solve(const locat& p)
{
if (p == end()) return true;
mark(p) = road;
(*this)(p) = way;
ans.push(p);
for (auto& i : operat)
{
auto tmp = i(p);
if (isIn(tmp) && (*this)(tmp) != wall
&& mark(tmp) != road && solve(tmp)) {
return true;
}
}
ans.pop();
mark(p) = wall;
(*this)(p) = road;
return false;
}
主函數(shù)文件（測(cè)試用）：
#include"Maze.h"
int main(int argc, char* argv[])
{
jmc::Solute s(30, 30);
return 0;
}
運(yùn)行截圖：
輸出解決路徑：
當(dāng)然這里也可以寫成展示每一步走的動(dòng)畫的樣子，加個(gè)延時(shí)與清屏就可以了這里就不演示了。
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了C++中的string類型，在C++當(dāng)中，除了char 類型，還有專門的字符串類型，就叫做string，下面文字將圍繞其相關(guān)資料展開詳細(xì)內(nèi)容,需要的朋友可以參考一下，希望對(duì)你有所幫助2021-11-11
關(guān)于虛函數(shù)實(shí)現(xiàn)多態(tài)的原理及分析
這篇文章主要介紹了C++中如何實(shí)現(xiàn)多態(tài)問題，具有很好的參考價(jià)值，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02
這篇文章主要為大家詳細(xì)介紹了C語言編寫一個(gè)鏈表，文中安裝步驟介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-05-05
利用C語言結(jié)構(gòu)體實(shí)現(xiàn)通訊錄
這篇文章主要為大家詳細(xì)介紹了利用C語言結(jié)構(gòu)體實(shí)現(xiàn)通訊錄，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-01-01
c++ priority_queue用法入門超詳細(xì)教程
priority_queue即優(yōu)先級(jí)隊(duì)列,它的使用場(chǎng)景很多,它底層是用大小根堆實(shí)現(xiàn)的,可以用log(n)的時(shí)間動(dòng)態(tài)地維護(hù)數(shù)據(jù)的有序性,這篇文章主要介紹了c++ priority_queue用法入門超詳細(xì)教程,需要的朋友可以參考下2023-12-12
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)2048游戲代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-05-05
這篇文章主要為大家詳細(xì)介紹C++?Queue隊(duì)列類模版實(shí)例，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
這篇文章主要介紹了c++中vector的使用和模擬實(shí)現(xiàn),本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-04-04
C語言實(shí)現(xiàn)隨機(jī)抽獎(jiǎng)程序
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)隨機(jī)抽獎(jiǎng)程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-09-09
這篇文章主要介紹了C++基于回溯法解決八皇后問題,簡(jiǎn)單描述了八皇后問題,以及回溯法的原理與解決八皇后問題的相關(guān)操作技巧,需要的朋友可以參考下2017-11-11