基于C++解决迷宫求解问题【100012656】

# 1 需求分析 ## 1.1问题描述 以一个 *m × n* 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序， 对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 ## 1.2涉及知识点 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路径退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。 为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。 ## 1.3基本要求 1. 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组 (*i, j, d*) 的形式输出。其中：(*i, j*) 指示迷宫中的一个坐标，*d* 表示走到下一坐标的方向。如，对于图 [1]所示的迷宫，输出一条通路为：(1*,* 1*,* 0)*,* (1*,* 2*,* 1)*,* (2*,* 2*,* 1)*,* (3*,* 2*,* 2)*,* (3*,* 1*,* 1)*, · · ·* 2. 编写递归形式的算法，求得迷宫中所有可能的通路。 3. 以方阵形式输出迷宫及其通路。  图 1: 迷宫示例 # 2 概要设计 ## 2.1数据结构 ### 2.1.1坐标位置类 坐标是一个重要的数据结构，它记录了方块的位置信息，是计算机探索路径的关键依据。 |**Pos**| | :-: | |<p>+ i : int</p><p>+ j : int</p>| |+ Pos()| |+ Pos(int i, int j)| |+ operator==(const Pos& right) : bool| |+ to\_String(): string| 坐标类数据成员：（i，j）表示一个坐标，i 和 j 均为 int 类型。 坐标类函数成员： 1. Pos()，构造函数，初始化一个坐标 2. operator==()，重载“==”运算符，用于判断两个位置是否相等 3. to\_String()，将坐标信息转换为字符串 ### 2.1.2通道块类 假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，那么应该有一个辅助变量指示计算机下一次要达到的位置。“下一位置”可以是当前位置的东、南、西、北方向相邻的方块，我们只记录即将转向的方向值就可以了。 于是，将坐标位置和“从此通道块走向下一通道块的方向”封装成一个通道块类。 |**Block**| | :-: | |<p>+ ord : int</p><p>+ seat : Pos</p><p>+ di : int</p>| |<p>+ Block()</p><p>+ Block(int ord, Pos seat)</p><p>+ setBlock(int ord, Pos seat, int di)</p><p>+ to\_String() : string</p><p>+ operator<<(ostream& out, Block block) : ostream&</p>| 通道块类数据成员： 1. ord，通道块在路径上的“序号” 2. seat，通道块在迷宫中的“坐标” 3. di，从此通道块走向下一通道块的方向，规定其值取 0、1、2、3，分别代表东、南、西、北 通道块类函数成员： 1. Block()，构造函数，初始化一个通道块 2. setBlock()，设置通道块 3. to\_String()，将通道块信息转换为字符串 4. operator«()，重载“«”运算符, 用于输出通道块类信息到输出流中 ### 2.1.3迷宫类 将迷宫的行数、列数、迷宫矩阵，封装成一个迷宫类。此处规定迷宫矩阵中障碍的值为“@”，通路的值为“.”，计算机探索后，经过的路径的值为“\*”。 |**Maze**| | :-: | |<p>- r : int</p><p>- c : int</p><p>- map : char[][]</p>| |<p>+ Maze()</p><p>+ Maze(int r, int c, char map[][])</p><p>+ getRow() : int</p><p>+ getCol() : int</p><p>+ setRow()</p><p>+ setCol()</p><p>+ setMapValue(Pos pos, char value)</p><p>+ getMapValue(Pos pos) : char</p><p>+ canPass(Pos pos) : bool</p>| 迷宫类数据成员： 1. r，行数 2. c，列数 map，迷宫矩阵 迷宫类函数成员： 1. Maze()，构造函数，初始化迷宫 2. getRow()，获取行数 3. getCol()，获取列数 4. setRow()，设置行数 5. setCol()，设置列数 6. setMapValue()，设置迷宫矩阵某坐标元素值 7. getMapValue()，获取迷宫矩阵某坐标元素 8. canPass()，某坐标是否通路 ### 2.1.4栈节点类 栈节点类，组成栈结构的基本单元，此处选用链栈结构。 |**Node<T>**| | :-: | |<p>- data: T</p><p>- next: Node<T>\*</p>| |<p>+ Node()</p><p>+ Node(T data, Node<T>\* next = nullptr)</p><p>+ getData() : T</p><p>+ setNext(Node<T>\* next)</p><p>+ getNext() : Node<T>\*</p>| 栈节点类的数据成员： 1. data，数据域 2. next，指针域，指向下一节点 栈节点类的函数成员： 1. Node()，构造函数，初始化一个节点 2. getData()，获取数据域 3. setNext()，设置下一节点 4. getNext()，获取下一节点 ### 2.1.5栈类 栈（Stack），是限定仅在表尾进行插入或删除的线性数据结构，具有“后进先出”的特点。这符合迷宫问题求解时需在任何位置上都能沿原路退回的要求。 这里使用栈的链式结构。 |**Stack<T>**| | :-: | |<p>- top: Node<T>\*</p><p>- size: int</p>| |<p>+ Stack()</p><p>*∼* Stack()</p><p>+ getSize() : int</p><p>+ isEmpty() : bool</p><p>+ push(T data)</p><p>+ pop()</p><p>+ pop(T &e)</p><p>+ getTop() : Node<T>&</p><p>+ print()</p>| 栈类的数据成员： 0. top，栈顶，链栈头指针 0. size，栈大小 (节点个数) 栈类的函数成员： 0. Stack()，构造函数，初始化一个栈 0. *∼*Stack()，析构函数，释放栈 0. getSize()，获取栈长 0. isEmpty()，判断栈是否为空 0. push()，入栈 0. pop()，出栈 0. getTop()，获取栈顶 0. print()，将栈输出到 cout 对象中 ## 2.2程序模块 1. 输入模块 从标准输入或文件中输入迷宫矩阵。 2. 非递归搜索算法模块 使用栈这种数据结构进行路径的非递归搜索，求出一条路径或判定是否存在通路。该算法的设计见算法1。  3. 递归搜索算法模块 使用栈这种数据结构进行路径的递归搜索，求出所有通路路径。 该算法的设计见算法2。  # 3 详细设计 ## 3.1类的函数实现 ### 3.1.1坐标位置类 坐标位置类的函数实现如代码 1 所示。 ```c++ // 重载 "==" 运算符， 用于判断两个位置是否相等 bool Pos :: operator ==( const Pos & right) const { return (i == right.i && j == right.j); } // 构造函数 Pos :: Pos () : Pos(0, 0) {} Pos :: Pos( int i, int j) { this ->i = i; this ->j = j; } // 将坐标信息转换为字符串 std :: string Pos :: to_String () { return ( std :: to_string (i) + "," + std :: to_string (j)); } ``` 代码 1: Pos 类的实现 ### 3.1.2通道块类 通道块类的函数实现如代码 2 所示。 ```c++ // 构造函数 Block :: Block () = default ; Block :: Block ( int ord , Pos seat , int di) { setBlock (ord , seat , di); } // 设置通道块 void Block :: setBlock ( int ord , Pos seat , int di){ this -> ord = ord ; this -> seat = seat; this ->di = di; } // 将通道块信息转换为字符串 std :: string Block :: to_String () { return "(" + seat. to_String () + "," + std :: to_string (di) + " )"; } // 重载"<<" 运算符, 用于输出通道块类信息到输出流中 std :: ostream & operator <<( std :: ostream & output , Block block ) { output << block . to_String (); return output; } ``` 代码 2: Block 类的实现 ### 3.1.3迷宫类 迷宫类的函数实现如代码 3 所示。 ```c++ //构造函数 Maze:: Maze () = default ; Maze:: Maze ( int r, int c, char map [ MAXLEN ][ MAXLEN ]) this ->r = r; { th