老鼠迷宫文档

【知识点详解】 本文档介绍的是一个使用Java编写的“老鼠迷宫”程序，它通过一个二维数组表示迷宫，寻找从入口到出口的路径。这个程序的核心算法是基于深度优先搜索（DFS）策略的，利用栈来存储路径，以便回溯。 1. **数据结构与类的设计** - `MiGong` 类是程序的主要类，它包含了一个二维数组 `maze` 来存储迷宫地图，以及一个 `Stack<Point>` `stack` 用于保存路径。 - `Point` 是一个内部类，用于表示迷宫中的位置，包括 `x` 和 `y` 坐标，并重写了 `equals()` 方法来比较两个点是否相同，以及 `toString()` 方法以字符串形式展示点的坐标。 2. **初始化迷宫** - 在 `main` 方法中，通过 `Scanner` 读取用户输入的迷宫数据，并创建一个 `MiGong` 实例，将迷宫地图传入构造函数。 3. **深度优先搜索（DFS）算法** - `go()` 方法实现了DFS算法，入口点是 `(0, 0)`，出口点是 `maze.length - 1, maze[0].length - 1`。 - 使用一个变量 `curNode` 表示当前节点，`nextNode` 作为目标节点，初始时两者都指向入口。 - 在循环中，通过检查上下左右四个方向的邻居节点，如果找到可通行的路径，就更新目标节点的位置；否则，如果当前节点无路可走，将栈顶元素弹出，即回溯到上一步。 - 为了标记已经访问过的节点，将值设为2；对于死路，标记为3。 - 当找到出口时，将出口点压入栈中，标记为已走，然后输出路径。 4. **代码逻辑分析** - 如果栈为空，表示无法到达出口，程序输出 "Non solution" 并终止。 - 循环过程中，通过 `stack.push(curNode)` 将当前节点压入栈，以保留路径信息。 - 通过 `stack.pop()` 实现回溯，当找到新路径时，再用 `stack.push(curNode)` 更新路径。 5. **迷宫地图的表示** - 迷宫地图使用二维数组 `maze`，其中0表示可通过，1表示墙壁，2表示已走过，3表示死路。 - 示例中给出的迷宫部分数据为： ``` 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, ``` 6. **运行与输出** - 用户可以通过输入迷宫数据来运行程序，程序会输出一条从入口到出口的可行路径。 - 在示例中，程序会输出迷宫的一条可行路径，即所有经过的点的坐标。 这个Java程序实现了一个简单的老鼠迷宫求解器，通过深度优先搜索策略在给定的二维数组迷宫中找到一条从起点到终点的路径。同时，程序还考虑了路径的记录和输出，以及死路的处理，体现了算法设计和数据结构的应用。