c/c++语言开发共享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;  }