C++實現迷宮生成與解決

#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; } //返回一維坐標 
 rowType x(const rowType& r) { loc.first = r; return loc.first; }//修改並返回一維坐標 
 calType y(void)const { return loc.second; } //返回二維坐標
 calType y(const calType& c) { loc.second = c; return loc.second; }//修改並返回二維坐標
 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); // 隨機生成一個迷宮，采用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(); } // 返回迷宮的行數
 calType cal(void) { return xyMsg.y(); } // 返回迷宮的列數
 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); //返回一個路周圍的墻
 locats findRoad(const locat& p); //返回一個墻周圍的路

 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
 << "請輸入起點的行坐標與列坐標:";
 std::cin >> tmpR >> tmpC;
 (*this)(end()(tmpR, tmpC)) = way;
 std::cout << "請輸入終點的行坐標與列坐標:";
 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{};
 };
}

#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))
{
 // 初始化隨機數生成器
 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;
 }
 }

 //隨機生成起點，把邊框分為四段
 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); //將起點對應到實際位置
 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); //隨機將一個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有未標記的，將此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;
}

#include"Maze.h"
int main(int argc, char* argv[])
{
 jmc::Solute s(30, 30);
 return 0;
}