迷宫问题（一）（C++版本）

一.深度遍历迷宫

深度遍历法针对的是找到迷宫中的一条对的路径，而不是找到多个路径，也就是说深度遍历法针对的是找一条可以出迷宫的路径，通常路径的特点和程序员对于四个方向的遍历顺序有关，通常程序员都会将四个走动方向的顺序编为：右->下->左->上。根据方向的特点可以得知迷宫通路的顺序，迷宫会一直向右探寻路径如果右边一直可以走，但前提也得小于迷宫的范围，如果右边无法探寻则向下探寻，向下探寻完后继续向右探寻，如此反复，则生成了一条路径。

迷宫的定义类：我们通常用‘0’表示节点可以通行而‘1’表示节点不可通行。通过上面的简述我们可以得知用栈的数据结构来实现迷宫通路的记录，我们可以将迷宫整个实现通过一个类来实现类中包含了公共的函数来实现迷宫各个部分和私有成员变量。我们可以分析得到类中函数的功能：

1.构造函数来实现迷宫的棋盘设计，也就是迷宫的行与列。

2.设置迷宫的节点信息，所谓的节点信息也就是每个节点的右下左上都设置为不可通行以便后面的路径搜索来重新设置节点是否可以通行。

3.设置迷宫路径如果节点信息为0则设置为YES可通行，如果节点为1则不必要修改节点信息因为第二步已经将所有节点信息更改为了NO。

4.搜索路径，搜索路径通过栈来解决，某个节点某个方向可以通行时我们就将它入栈如果四个方向都无法通行时就将该节点出栈，如此往复则可以得到一条路径走出迷宫，但如果没有路径出迷宫时栈就会一直出栈直到栈空，此时就无法找到一条通路了。

5.展示搜索后的路径，这是迷宫类中的最后一个函数，作用就是通过栈来还原可走路径，我们需要将可走路径的节点更改为‘*’，其余节点则无需更改。

需要完成的就是上方伪代码，只需要完成函数的实现就行了。

二 .代码实现

1.类的实现：

#include<iostream>
using namespace std;
#include<stack>
//定义迷宫每一个节点的四个方向
const int RIGHT = 0;
const int DOWN = 1;
const int LEFT = 2;
const int UP = 3;//迷宫每一个节点方向的数量
const int WAY_NUM = 4;//定义节点行走的状态
const int YES = 5;
const int NO = 6;//迷宫
class Maze
{
public://初始化迷宫，根据用户输入的行列数，生成储存迷宫路径信息的二维数组Maze(int row, int col):_row(row),_col(col){_pMaze = new Node * [_row];for (int i = 0; i < _row; ++i){_pMaze[i] = new Node[_col];}}//初始化迷宫路径节点信息void initNode(int x, int y, int val){_pMaze[x][y]._x = x;_pMaze[x][y]._y = y;_pMaze[x][y]._val = val;for (int i = 0; i < WAY_NUM; i++){_pMaze[x][y]._state[i] = NO;}}//初始化迷宫0节点四个方向的行走状态void setNodeState(){for (int i = 0; i < _row; i++){for (int j = 0; j < _col; j++){if (_pMaze[i][j]._val == 1){continue;}if (j < _col - 1 && _pMaze[i][j + 1]._val == 0){_pMaze[i][j]._state[RIGHT] = YES;}if (i < _row - 1 && _pMaze[i + 1][j]._val == 0){_pMaze[i][j]._state[DOWN] = YES;}if (j > 0 && _pMaze[i][j-1]._val == 0){_pMaze[i][j]._state[LEFT] = YES;}if (i > 0 && _pMaze[i-1][j]._val == 0){_pMaze[i][j]._state[UP] = YES;}}}}//深度搜索迷宫路径void searchMazePath(){if (_pMaze[0][0]._val == 1){return;}_stack.push(_pMaze[0][0]);while (!_stack.empty()){Node top = _stack.top();int x = top._x;int y = top._y;//已经找到右下角出口得到迷宫路径if (x == _row - 1 && y == _col - 1){return;}//向右找if (_pMaze[x][y]._state[RIGHT] == YES){_pMaze[x][y]._state[RIGHT] = NO;_pMaze[x][y + 1]._state[LEFT] = NO;_stack.push(_pMaze[x][y + 1]);continue;}//向下找if (_pMaze[x][y]._state[DOWN] == YES){_pMaze[x][y]._state[DOWN] = NO;_pMaze[x+1][y]._state[UP] = NO;_stack.push(_pMaze[x+1][y]);continue;}//向左找if (_pMaze[x][y]._state[LEFT] == YES){_pMaze[x][y]._state[LEFT] = NO;_pMaze[x][y-1]._state[RIGHT] = NO;_stack.push(_pMaze[x][y-1]);continue;}//向上找if (_pMaze[x][y]._state[UP] == YES){_pMaze[x][y]._state[UP] = NO;_pMaze[x - 1][y]._state[DOWN] = NO;_stack.push(_pMaze[x - 1][y]);continue;}_stack.pop();}}//打印迷宫路径搜索结构void showMazePath(){if (_stack.empty()){cout << "不存在一条迷宫路径！" << endl;}else{while (!_stack.empty()){Node top = _stack.top();_pMaze[top._x][top._y]._val = '*';_stack.pop();}for (int i = 0; i < _row; i++){for (int j = 0; j < _col; j++){if (_pMaze[i][j]._val == '*'){cout << "* ";}else{cout << _pMaze[i][j]._val << " ";}}cout << endl;}}}
private:struct Node{int _x;int _y;int _val;//节点的值int _state[WAY_NUM];//记录节点四个方向的状态};Node** _pMaze;//动态生成迷宫路径int _row;int _col;stack<Node>_stack;//栈结构，辅助深度搜索迷宫路径
};

2.main函数的实现

int main()
{cout << "请输入迷宫的行列数（例如:10 10）：";int row, col, data;cin >> row >> col;Maze maze(row, col);cout << "请输入迷宫路径信息（0表示可以走，1表示不可以走）：" << endl;for (int i = 0; i < row; i++){for (int j = 0; j < col; j++){cin >> data;maze.initNode(i, j, data);}}maze.setNodeState();maze.searchMazePath();maze.showMazePath();return 0;
}