迷宫中存在起点与终点，墙壁用数字2表示，行走路线用数字1表示，可行走的点用0表示。
#include <iostream>#include <map>#include <vector>#include <set>#include <iterator>using namespace std;//5（一）class CMaze{public:CMaze(){int iSize = 6;_maze_info.resize(iSize);for (int i = 0; i < iSize; ++i){for (int j = 0; j < iSize; ++j){if (i == 0 || j == 0 || i == iSize-1 || j == iSize-1){_maze_info[i].push_back(2);}else{_maze_info[i].push_back(0);}}}_maze_info[1][2] = 2;_maze_info[2][2] = 2;_maze_info[3][2] = 2;//_maze_info[4][2] = 2;_begin_point = make_pair<int, int>(1, 1);_end_point = make_pair<int, int>(4, 4);}bool findOutRoad(){//return findOutRoadOne(_begin_point.first, _begin_point.second);vector<pair<int, int>> veRoad;return findOutRoadAll(_begin_point.first, _begin_point.second, veRoad);}//是否可以走出去bool findOutRoadOne(int x, int y){//cout << "---------------------" << endl;//show();if (x == _end_point.first && y == _end_point.second)return true;_maze_info[x][y] = 1;if (_maze_info[x - 1][y] == 0) return findOutRoadOne(x - 1, y);else if (_maze_info[x][y - 1] == 0) return findOutRoadOne(x, y - 1);else if (_maze_info[x + 1][y] == 0) return findOutRoadOne(x + 1, y);else if (_maze_info[x][y + 1] == 0) return findOutRoadOne(x, y + 1);elsereturn false;}//路线bool findOutRoadAll(int x, int y, std::vector<pair<int, int>> &road){if (x == _end_point.first && y == _end_point.second){for (auto &it : road){cout << "road: " << it.first << " - " << it.second << endl;}cout << endl;return true;}bool bRet = false;_maze_info[x][y] = 1;road.push_back(std::make_pair(x-1, y));if (_maze_info[x - 1][y] == 0) bRet = findOutRoadAll(x - 1, y, road);if (bRet) return true;road.pop_back();road.push_back(std::make_pair(x, y-1));if (_maze_info[x][y - 1] == 0) bRet = findOutRoadAll(x, y - 1, road);if (bRet) return true;road.pop_back();road.push_back(std::make_pair(x + 1, y));if (_maze_info[x + 1][y] == 0) bRet = findOutRoadAll(x + 1, y, road);if (bRet) return true;road.pop_back();road.push_back(std::make_pair(x, y+1));if (_maze_info[x][y + 1] == 0) bRet = findOutRoadAll(x, y + 1, road);return bRet;}void show(){for (int i = 0; i < _maze_info.size(); ++i){for (int j = 0; j < _maze_info[i].size(); ++j)cout << _maze_info[i][j] << " ";cout << endl;}cout << endl;}vector<vector<int>> _maze_info;pair<int, int> _begin_point;//开始pair<int, int> _end_point; //结束};
以上代码只能表示是否出去与其中的路线打印，但是并不是最近的路线。寻找最近路线，需要每次向着终点的方向前进，可以使用简化版A*算法。
class AStar{public:struct stRoadInfo{int iPosx = 0;int iPosy = 0;int iFPosx = 0;int iFPosy = 0;int iVal = 0;};AStar(){int iSize = 6;_maze_info.resize(iSize);for (int i = 0; i < iSize; ++i){for (int j = 0; j < iSize; ++j){if (i == 0 || j == 0 || i == iSize - 1 || j == iSize - 1){_maze_info[i].push_back(2);}else{_maze_info[i].push_back(0);}}}_maze_info[1][2] = 2;_maze_info[2][2] = 2;_maze_info[3][2] = 2;//_maze_info[4][2] = 2;_begin_point = make_pair<int, int>(1, 1);_end_point = make_pair<int, int>(4, 4);}bool find_road(){stRoadInfo info;build_roadinfo(_begin_point, std::make_pair(0, 0), info);openlist.insert(std::make_pair(info.iVal, info));while (1){auto itopen = openlist.begin();if (itopen == openlist.end()){return false;}std::pair<int, int> pairtmp = std::make_pair(itopen->second.iPosx, itopen->second.iPosy);closelist.insert(std::make_pair(pairtmp, itopen->second));openlist.erase(itopen);if (get_instance(pairtmp) == 0){while (pairtmp.first != 0 && pairtmp.second != 0){auto it = closelist.find(pairtmp);if (it == closelist.end()) break;cout << pairtmp.first << " - " << pairtmp.second << endl;pairtmp = std::make_pair(it->second.iFPosx, it->second.iFPosy);}return true;}//方向if (_maze_info[pairtmp.first - 1][pairtmp.second] == 0 && closelist.find(std::make_pair(pairtmp.first - 1, pairtmp.second)) == closelist.end()){stRoadInfo info;build_roadinfo(std::make_pair(pairtmp.first-1, pairtmp.second), pairtmp, info);openlist.insert(std::make_pair(info.iVal, info));}if (_maze_info[pairtmp.first][pairtmp.second-1] == 0 && closelist.find(std::make_pair(pairtmp.first, pairtmp.second-1)) == closelist.end()){stRoadInfo info;build_roadinfo(std::make_pair(pairtmp.first, pairtmp.second-1), pairtmp, info);openlist.insert(std::make_pair(info.iVal, info));}if (_maze_info[pairtmp.first + 1][pairtmp.second] == 0 && closelist.find(std::make_pair(pairtmp.first + 1, pairtmp.second)) == closelist.end()){stRoadInfo info;build_roadinfo(std::make_pair(pairtmp.first + 1, pairtmp.second), pairtmp, info);openlist.insert(std::make_pair(info.iVal, info));}if (_maze_info[pairtmp.first][pairtmp.second+1] == 0 && closelist.find(std::make_pair(pairtmp.first, pairtmp.second+1)) == closelist.end()){stRoadInfo info;build_roadinfo(std::make_pair(pairtmp.first, pairtmp.second+1), pairtmp, info);openlist.insert(std::make_pair(info.iVal, info));}}}void build_roadinfo(std::pair<int, int> &pos, std::pair<int, int> &fpos, AStar::stRoadInfo &info){info.iPosx = pos.first;info.iPosy = pos.second;info.iFPosx = fpos.first;info.iFPosy = fpos.second;info.iVal = get_instance(pos);}int get_instance(std::pair<int, int> &begin){return abs(begin.first - _end_point.first) + abs(begin.second - _end_point.second);}private:vector<vector<int>> _maze_info;pair<int, int> _begin_point;//开始pair<int, int> _end_point; //结束std::multimap<int, stRoadInfo> openlist;std::map<std::pair<int, int>, stRoadInfo> closelist;};
