随州网站推广哪家权威,20个外国平面设计网站,wordpress 媒体库 群晖,wordpress修改博客深度优先搜索迷宫路径 问题描述
我们需要编写一个程序#xff0c;通过深度优先搜索#xff08;DFS#xff09;找到从迷宫左上角到右下角的一条通路。 迷宫的表示#xff1a; 迷宫由 0 和 1 构成的二维数组表示。0 表示可以走的路径#xff0c;1 表示障碍。用户输入迷宫的…深度优先搜索迷宫路径 问题描述
我们需要编写一个程序通过深度优先搜索DFS找到从迷宫左上角到右下角的一条通路。 迷宫的表示 迷宫由 0 和 1 构成的二维数组表示。0 表示可以走的路径1 表示障碍。用户输入迷宫的行列数和迷宫的内容。 功能需求 找到一条从左上角到右下角的路径。如果路径存在用 * 标记路径并打印迷宫。如果路径不存在打印提示信息。 代码实现思路
1. 核心算法
我们使用深度优先搜索DFS来遍历迷宫
优先级右 → 下 → 左 → 上。使用栈存储路径 当前节点可以继续探索时入栈。如果遇到死路则回退出栈。
2. 数据结构 节点 (Node) 坐标 (x, y)。值 (value)通路 (PATH) 或障碍 (WALL)。四个方向的行走状态 (direction)是否可以向 右、下、左、上 移动。 迷宫 (Maze) 包含节点的二维数组。动态分配内存以支持不同大小的迷宫。 栈 (std::stack) 存储路径节点便于回退操作。
3. 流程 输入 用户输入行数和列数随后输入迷宫数据。 初始化 设置每个节点的方向状态右、下、左、上是否可行。初始化所有节点的值PATH 或 WALL。 搜索路径 如果入口或出口为障碍 (WALL)直接输出“无路径”。否则从起点 (0, 0) 开始搜索 判断当前节点四个方向是否可行。可行方向入栈不可行则回退出栈。 输出 如果找到路径打印迷宫将路径标记为 *。如果找不到路径提示“无路径”。 完整代码
#include iostream
#include stack// 定义方向常量
enum Direction { RIGHT 0, DOWN, LEFT, UP };// 定义状态常量
const int YES 4; // 表示该方向可走
const int NO 5; // 表示该方向不可走// 定义迷宫单元状态
enum CellState { PATH 0, WALL 1 }; // PATH 表示通路WALL 表示障碍// 节点结构体表示迷宫中的一个单元
struct Node {int x, y; // 坐标CellState value; // 值PATH 表示通路WALL 表示障碍int direction[4]; // 四个方向RIGHT, DOWN, LEFT, UP值为 YES 表示能走NO 表示不能走
};// 迷宫类
class Maze {
private:int rows, cols; // 迷宫行数和列数Node** grid; // 动态二维数组存储迷宫std::stackNode* path; // 栈用于深度优先搜索路径public:Maze(int r, int c) : rows(r), cols(c) {grid new Node*[rows];for (int i 0; i rows; i) {grid[i] new Node[cols];}}~Maze() {for (int i 0; i rows; i) {delete[] grid[i];}delete[] grid;}// 初始化迷宫void initializeMaze() {std::cout Enter the maze (0 for path, 1 for obstacle):\n;for (int i 0; i rows; i) {for (int j 0; j cols; j) {int value;std::cin value;grid[i][j].value (value 0) ? PATH : WALL; // 使用枚举替代数字grid[i][j].x i;grid[i][j].y j;for (int k 0; k 4; k) {grid[i][j].direction[k] NO; // 初始状态不可走}}}}// 设置每个节点四个方向的状态void setNodeDirections() {for (int i 0; i rows; i) {for (int j 0; j cols; j) {if (grid[i][j].value WALL) continue; // 如果是障碍跳过// 右方向if (j 1 cols grid[i][j 1].value PATH) grid[i][j].direction[RIGHT] YES;// 下方向if (i 1 rows grid[i 1][j].value PATH) grid[i][j].direction[DOWN] YES;// 左方向if (j - 1 0 grid[i][j - 1].value PATH) grid[i][j].direction[LEFT] YES;// 上方向if (i - 1 0 grid[i - 1][j].value PATH) grid[i][j].direction[UP] YES;}}}// 深度优先搜索迷宫路径bool searchPath() {if (grid[0][0].value WALL || grid[rows - 1][cols - 1].value WALL) return false;path.push(grid[0][0]); // 起点入栈while (!path.empty()) {Node* current path.top();int x current-x, y current-y;// 判断是否到达终点if (x rows - 1 y cols - 1) return true;bool moved false;// 右方向if (current-direction[RIGHT] YES grid[x][y 1].direction[LEFT] YES) {current-direction[RIGHT] NO;grid[x][y 1].direction[LEFT] NO;path.push(grid[x][y 1]);moved true;}// 下方向else if (current-direction[DOWN] YES grid[x 1][y].direction[UP] YES) {current-direction[DOWN] NO;grid[x 1][y].direction[UP] NO;path.push(grid[x 1][y]);moved true;}// 左方向else if (current-direction[LEFT] YES grid[x][y - 1].direction[RIGHT] YES) {current-direction[LEFT] NO;grid[x][y - 1].direction[RIGHT] NO;path.push(grid[x][y - 1]);moved true;}// 上方向else if (current-direction[UP] YES grid[x - 1][y].direction[DOWN] YES) {current-direction[UP] NO;grid[x - 1][y].direction[DOWN] NO;path.push(grid[x - 1][y]);moved true;}if (!moved) path.pop(); // 如果四个方向都不能走回退}return false; // 栈为空未找到路径}// 打印迷宫路径void printPath() {// 将路径标记为 *while (!path.empty()) {Node* node path.top();path.pop();grid[node-x][node-y].value PATH; // 使用 PATH 表示路径}// 输出迷宫for (int i 0; i rows; i) {for (int j 0; j cols; j) {if (grid[i][j].value PATH) {std::cout *;} else {std::cout grid[i][j].value;}}std::cout std::endl;}}
};int main() {int rows, cols;std::cout Enter maze dimensions (rows and columns): ;std::cin rows cols;Maze maze(rows, cols);maze.initializeMaze();maze.setNodeDirections();if (maze.searchPath()) {maze.printPath();} else {std::cout No path exists in the maze.\n;}return 0;
}关键点总结 避免魔法数字 使用 CellState (PATH, WALL) 表示单元状态。使用 Direction 枚举RIGHT, DOWN, LEFT, UP表示方向。 清晰的逻辑 每个方向的逻辑右、下、左、上清晰明确。通过栈实现深度优先搜索并在死路时回退。 动态分配二维数组 根据用户输入动态分配内存提高灵活性。 代码可读性高 枚举和常量的使用使代码更易读、更易维护。 扩展性强 可轻松修改或增加方向、迷宫规则等逻辑。 运行示例
输入
Enter maze dimensions (rows and columns): 5 5
Enter the maze (0 for path, 1 for obstacle):
0 1 0 0 0
0 1 0 1 0
0 0 0 1 0
0 1 1 1 0
0 0 0 0 0输出
*****0
*111*0
*000*0
*111*0
*****0如果路径不存在输出
No path exists in the maze.深度优先搜索DFS迷宫路径算法详细解释 DFS 基本概念
深度优先搜索DFS是一种用于遍历或搜索图或树结构的算法。它优先沿着每一个可能的分支路径深入直到到达不可再继续的节点然后回退回溯到上一个节点探索未访问的分支。
在迷宫路径问题中可以将迷宫看作一个二维网格每个格子是一个节点相邻的格子通过边连接。DFS 的目标是在起点和终点之间找到一条路径。 问题描述 输入 一个二维数组表示迷宫 0 表示可以通行的路径。1 表示障碍不能通行。 起点 (0, 0) 和终点 (rows-1, cols-1)。 目标 找到一条从起点到终点的路径。如果找到路径用 * 标记路径并打印迷宫。如果不存在路径打印“无路径”。 DFS 核心思想 递归或栈实现 DFS 通过递归或栈来模拟路径搜索。每次探索当前节点的某个方向如果该方向可以走就继续深入。如果到达死胡同则回退到上一个节点探索其他未访问的方向。 避免重复访问 在每次移动到新节点时标记当前节点为“已访问”防止重复探索和回头路。可以通过修改节点状态或方向状态实现。 终止条件 如果到达终点 (rows-1, cols-1)返回成功。如果所有路径都探索完仍未到达终点返回失败。 DFS 算法步骤 初始化迷宫 输入迷宫的大小和内容。用 Node 结构表示迷宫中的每个格子存储格子的坐标、状态路径或障碍以及四个方向的可行性。 设置方向优先级 使用固定顺序右Right、下Down、左Left、上Up。通过数组 dx 和 dy 表示方向的坐标变化例如 右dx 0, dy 1下dx 1, dy 0 搜索过程 从起点 (0, 0) 开始将其加入路径栈。按顺序检查四个方向 如果某方向可以走 标记当前节点的方向为不可走。标记相邻节点从当前方向来的状态为不可走。将相邻节点入栈。继续深入探索。 如果四个方向都不能走则回退出栈返回上一个节点继续探索。 终止条件 找到终点时路径栈中的节点即为完整路径。栈为空时表示无路径。 输出路径 如果找到路径打印迷宫并用 * 标记路径。如果无路径打印提示信息。 伪代码
DFS(迷宫, 起点, 终点):如果起点或终点是障碍:返回“无路径”栈.push(起点)while 栈不为空:当前节点 栈顶如果当前节点是终点:返回路径否则:按顺序检查当前节点的 4 个方向:如果某方向可走:- 更新当前节点和相邻节点的状态防止回头路- 相邻节点入栈- 跳过后续方向break如果所有方向都不能走:当前节点出栈回退如果循环结束仍未找到终点:返回“无路径”详细过程解析
假设迷宫如下
0 1 0 0 0
0 1 0 1 0
0 0 0 1 0
0 1 1 1 0
0 0 0 0 0起点 (0, 0) 入栈 栈[(0, 0)]。从 (0, 0) 开始按顺序探索 右障碍。下可走入栈。 当前节点 (1, 0) 栈[(0, 0), (1, 0)]。按顺序探索 右障碍。下可走入栈。 当前节点 (2, 0) 栈[(0, 0), (1, 0), (2, 0)]。按顺序探索 右可走入栈。 当前节点 (2, 1) 栈[(0, 0), (1, 0), (2, 0), (2, 1)]。按顺序探索 右可走入栈。 当前节点 (2, 2) 栈[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]。按顺序探索 右障碍。下可走入栈。 当前节点 (3, 2) 栈[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2)]。按顺序探索 右障碍。下可走入栈。 当前节点 (4, 2) 栈[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2)]。按顺序探索 右可走入栈。 终点 (4, 4) 入栈 栈[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]。到达终点结束搜索。 关键点详解 方向状态的更新 每次移动后 当前节点的方向标记为不可走防止重复访问。相邻节点的回头方向标记为不可走防止回头。 栈的作用 栈保存当前路径节点用于实现深度优先搜索。当节点无法前进时回退到上一个节点继续探索。 搜索优先级 使用固定的方向顺序右、下、左、上确保路径唯一性。 边界条件 起点或终点为障碍时直接返回。每次移动前检查坐标是否越界。 时间与空间复杂度 时间复杂度 每个节点最多被访问一次复杂度为 O(n * m)其中 n 是行数m 是列数。 空间复杂度 栈中最多存储所有节点复杂度为 O(n * m)。 避免回头路的原理 每个节点的方向状态 每个节点有四个方向右、下、左、上用一个数组 direction[4] 表示 YES 表示该方向可以走。NO 表示该方向不可走。 双向更新 从当前节点走到相邻节点时 更新当前节点的该方向状态为 NO表示不能再次从该方向出发。同时更新相邻节点从回头方向来的状态为 NO表示不能回到当前节点。 目的 通过双向更新防止程序进入重复探索例如节点之间循环往返。 实现方式
以下代码展示了如何避免回头路取右方向为例
if (current-direction[RIGHT] YES grid[x][y 1].direction[LEFT] YES) {// 当前节点的右方向设置为不可走current-direction[RIGHT] NO;// 相邻节点的左方向设置为不可走grid[x][y 1].direction[LEFT] NO;// 将相邻节点入栈path.push(grid[x][y 1]);moved true;
}具体步骤
检查当前节点 current 的右方向是否可走direction[RIGHT] YES。检查相邻节点右边节点的左方向是否可走grid[x][y 1].direction[LEFT] YES。 这保证了两节点之间的状态一致。 更新状态 当前节点的右方向设置为 NO。右边节点的左方向设置为 NO。双向标记确保后续无法重复走该路径。 将右边节点入栈继续探索。 避免回头路的完整逻辑
在四个方向右、下、左、上中都应用类似逻辑。以下是完整实现
// 右方向
if (current-direction[RIGHT] YES grid[x][y 1].direction[LEFT] YES) {current-direction[RIGHT] NO;grid[x][y 1].direction[LEFT] NO;path.push(grid[x][y 1]);moved true;
}
// 下方向
else if (current-direction[DOWN] YES grid[x 1][y].direction[UP] YES) {current-direction[DOWN] NO;grid[x 1][y].direction[UP] NO;path.push(grid[x 1][y]);moved true;
}
// 左方向
else if (current-direction[LEFT] YES grid[x][y - 1].direction[RIGHT] YES) {current-direction[LEFT] NO;grid[x][y - 1].direction[RIGHT] NO;path.push(grid[x][y - 1]);moved true;
}
// 上方向
else if (current-direction[UP] YES grid[x - 1][y].direction[DOWN] YES) {current-direction[UP] NO;grid[x - 1][y].direction[DOWN] NO;path.push(grid[x - 1][y]);moved true;
}避免回头路的效果 走过的方向 每次从一个节点走向另一个节点时都会标记双向路径为“不可走”。例如从 (0, 0) 走到 (0, 1) 后 (0, 0) 的右方向 direction[RIGHT] 被标记为 NO。(0, 1) 的左方向 direction[LEFT] 被标记为 NO。 防止重复探索 在后续探索中如果程序回退到 (0, 1)由于其左方向 direction[LEFT] 已标记为 NO程序不会再返回 (0, 0)。 避免循环 如果没有双向标记程序可能陷入循环例如 (0, 0) → (0, 1) → (0, 0) 不断往返。 更新方向状态的逻辑图解
以下是避免回头路的具体过程假设我们从 (0, 0) 开始探索
初始状态
方向状态 (0, 0):
RIGHT YES, DOWN YES, LEFT NO, UP NO
方向状态 (0, 1):
RIGHT YES, DOWN YES, LEFT YES, UP NO第一次移动从 (0, 0) → (0, 1)
当前节点 (0, 0) 的 RIGHT 被设置为 NO。相邻节点 (0, 1) 的 LEFT 被设置为 NO。节点 (0, 1) 入栈。
更新后的状态
方向状态 (0, 0):
RIGHT NO, DOWN YES, LEFT NO, UP NO
方向状态 (0, 1):
RIGHT YES, DOWN YES, LEFT NO, UP NO第二次移动从 (0, 1) → (1, 1)
当前节点 (0, 1) 的 DOWN 被设置为 NO。相邻节点 (1, 1) 的 UP 被设置为 NO。节点 (1, 1) 入栈。
更新后的状态
方向状态 (0, 1):
RIGHT YES, DOWN NO, LEFT NO, UP NO
方向状态 (1, 1):
RIGHT YES, DOWN YES, LEFT YES, UP NO走到死胡同时的回退
当一个节点的四个方向都不可走时执行出栈操作回到上一个节点。回退时不会选择已标记为 NO 的方向避免重复探索。
