迷宫程序实际上是图的遍历的应用，只是在本例中迷宫的每个入口都是只有4个方向（上下左右），而在图中每个顶点可以有任意个邻接顶点，邻接顶点之间也可以有回环。在遍历时可以使用递归调用（占用系统栈空间），也可以在遍历过程中把信息存入自己建立的容器（栈适合于深度优先遍历， 后进先出的特点）；从一个顶点v到他的未访问的邻接顶点有多个路径，既然深入下去一条，就需要记住其他几条路径（也就是v的其他未访问的邻接顶点），或者至少记住未访问的路径的所有公共顶点（也即v），这种会节省栈空间，但是略麻烦，需要重新寻找v的all adjacent vertex，如果graph存储为martrix，总体需要查找时间为O（V平方），如果为adjacent list结构总体需要O（E）。
在这个maze例子中就是用DFS深度优先遍历，直到找出出口。
边界border用1表示，通路用0表示，入口用m表示，出口用e表示，访问过标志用，表示。
#pragma once
#include <iostream>
#include <string>
#include <stack>
using namespace std;template<class T>
class Stack : public stack<T>
{
public:T pop(){T tmp = top();stack<T>::pop();return tmp;}
};class Cell
{friend class Maze;
public:Cell(int i = 0, int j = 0) : x(i), y(j) { }bool operator==(const Cell &c) const{return x == c.x && y == c.y;}
private:int x, y;
};class Maze {
public:Maze();void exitMaze();
private:Cell currentCell, exitCell, entryCell;const char exitMarker, entryMarker, visited, passage, wall;Stack<Cell> mazeStack;char **store; // array of strings;void pushUnvisited(int, int);int rows, cols;friend ostream& operator<< (ostream& out, const Maze& maze) {for (int row = 0; row <= maze.rows + 1; row++)out << maze.store[row] << endl;out << endl;return out;}
};Maze::Maze() : exitMarker('e'), entryMarker('m'), visited(','),
passage('0'), wall('1') {char str[80], *s;int col, row = 0;Stack<char*> mazeRows;cout << "Enter a rectangular maze using the following "<< "characters:\nm - entry\ne - exit\n1 - wall\n 0 - passage"<< "\nEnter one line at a time, end with ctrl-z:\n";while (cin >> str) {row++;cols = strlen(str);s = new char[cols + 3]; // two borders and a \0mazeRows.push(s);strcpy(s + 1, str);s[0] = s[cols + 1] = wall;s[cols + 2] = '\0';if (strchr(s, exitMarker) != nullptr)exitCell = Cell(row, strchr(s, exitMarker) - s);if (strchr(s, entryMarker) != nullptr)entryCell = Cell(row, strchr(s, entryMarker) - s);}rows = row;store = new char*[rows + 2]; // add up and bottem borderstore[0] = new char[cols + 3];store[rows + 1] = new char[cols + 3];while (!mazeRows.empty())store[row--] = mazeRows.pop();store[0][cols + 2] = store[rows + 1][cols + 2] = '\0';for (col = 0; col <= cols + 1; ++col) {store[0][col] = wall; // fill the borderline rows with 1s;store[rows + 1][col] = wall;}
}void Maze::pushUnvisited(int row, int col)
{if (store[row][col] == passage || store[row][col] == exitMarker)mazeStack.push(Cell(row, col));
}void Maze::exitMaze()
{int row, col;currentCell = entryCell;while (!(currentCell == exitCell)) {row = currentCell.x;col = currentCell.y;cout << *this;if (!(currentCell == entryCell))store[row][col] = visited;pushUnvisited(row - 1, col);pushUnvisited(row + 1, col);pushUnvisited(row, col - 1);pushUnvisited(row, col + 1);// 栈为空，说明已经没有可以试的路径了if (mazeStack.empty()) {cout << *this;cout << "Falure.\n";return;}elsecurrentCell = mazeStack.pop();}cout << *this;cout << "Success.\n";
}int main()
{Maze maze;maze.exitMaze();return 0;
}