深度优先搜索迷宫路径

深度优先搜索迷宫路径

---

问题描述

我们需要编写一个程序，通过深度优先搜索（DFS）找到从迷宫左上角到右下角的一条通路。

• 迷宫的表示：

  • 迷宫由 0 和 1 构成的二维数组表示。
  • 0 表示可以走的路径，1 表示障碍。
  • 用户输入迷宫的行列数和迷宫的内容。

• 功能需求：

  1. 找到一条从左上角到右下角的路径。
  2. 如果路径存在，用 * 标记路径并打印迷宫。
  3. 如果路径不存在，打印提示信息。

---

代码实现思路

1. 核心算法

我们使用深度优先搜索（DFS）来遍历迷宫：

• 优先级：右 → 下 → 左 → 上。
• 使用栈存储路径：
  • 当前节点可以继续探索时，入栈。
  • 如果遇到死路，则回退（出栈）。

2. 数据结构

• 节点 (Node)：

  • 坐标 (x, y)。
  • 值 (value)：通路 (PATH) 或障碍 (WALL)。
  • 四个方向的行走状态 (direction)：是否可以向 右、下、左、上 移动。

• 迷宫 (Maze)：

  • 包含节点的二维数组。
  • 动态分配内存以支持不同大小的迷宫。

• 栈 (std::stack)：

  • 存储路径节点，便于回退操作。

3. 流程

1. 输入：

   • 用户输入行数和列数，随后输入迷宫数据。

2. 初始化：

   • 设置每个节点的方向状态（右、下、左、上是否可行）。
   • 初始化所有节点的值（PATH 或 WALL）。

3. 搜索路径：

   • 如果入口或出口为障碍 (WALL)，直接输出“无路径”。
   • 否则，从起点 (0, 0) 开始搜索：
     • 判断当前节点四个方向是否可行。
     • 可行方向入栈；不可行则回退（出栈）。

4. 输出：

   • 如果找到路径，打印迷宫，将路径标记为 *。
   • 如果找不到路径，提示“无路径”。

---

完整代码

#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::stack<Node*> 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;
}

---

关键点总结

1. 避免魔法数字：

   • 使用 CellState (PATH, WALL) 表示单元状态。
   • 使用 Direction 枚举（RIGHT, DOWN, LEFT, UP）表示方向。

2. 清晰的逻辑：

   • 每个方向的逻辑（右、下、左、上）清晰明确。
   • 通过栈实现深度优先搜索，并在死路时回退。

3. 动态分配二维数组：

   • 根据用户输入动态分配内存，提高灵活性。

4. 代码可读性高：

   • 枚举和常量的使用，使代码更易读、更易维护。

5. 扩展性强：

   • 可轻松修改或增加方向、迷宫规则等逻辑。

---

运行示例

输入：

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 的目标是在起点和终点之间找到一条路径。

---

问题描述

1. 输入：

   • 一个二维数组表示迷宫：
     • 0 表示可以通行的路径。
     • 1 表示障碍，不能通行。
   • 起点 (0, 0) 和终点 (rows-1, cols-1)。

2. 目标：

   • 找到一条从起点到终点的路径。
   • 如果找到路径，用 * 标记路径并打印迷宫。
   • 如果不存在路径，打印“无路径”。

---

DFS 核心思想

1. 递归或栈实现：

   • DFS 通过递归或栈来模拟路径搜索。
   • 每次探索当前节点的某个方向，如果该方向可以走，就继续深入。
   • 如果到达死胡同，则回退到上一个节点，探索其他未访问的方向。

2. 避免重复访问：

   • 在每次移动到新节点时，标记当前节点为“已访问”，防止重复探索和回头路。
   • 可以通过修改节点状态或方向状态实现。

3. 终止条件：

   • 如果到达终点 (rows-1, cols-1)，返回成功。
   • 如果所有路径都探索完仍未到达终点，返回失败。

---

DFS 算法步骤

1. 初始化迷宫：

   • 输入迷宫的大小和内容。
   • 用 Node 结构表示迷宫中的每个格子，存储格子的坐标、状态（路径或障碍）以及四个方向的可行性。

2. 设置方向优先级：

   • 使用固定顺序：右（Right）、下（Down）、左（Left）、上（Up）。
   • 通过数组 dx 和 dy 表示方向的坐标变化，例如：
     • 右：dx = 0, dy = 1
     • 下：dx = 1, dy = 0

3. 搜索过程：

   • 从起点 (0, 0) 开始，将其加入路径栈。
   • 按顺序检查四个方向：
     1. 如果某方向可以走：
        • 标记当前节点的方向为不可走。
        • 标记相邻节点从当前方向来的状态为不可走。
        • 将相邻节点入栈。
        • 继续深入探索。
     2. 如果四个方向都不能走，则回退（出栈），返回上一个节点继续探索。

4. 终止条件：

   • 找到终点时，路径栈中的节点即为完整路径。
   • 栈为空时，表示无路径。

5. 输出路径：

   • 如果找到路径，打印迷宫并用 * 标记路径。
   • 如果无路径，打印提示信息。

---

伪代码

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

1. 起点 (0, 0) 入栈：

   • 栈：[(0, 0)]。
   • 从 (0, 0) 开始按顺序探索：
     • 右：障碍。
     • 下：可走，入栈。

2. 当前节点 (1, 0)：

   • 栈：[(0, 0), (1, 0)]。
   • 按顺序探索：
     • 右：障碍。
     • 下：可走，入栈。

3. 当前节点 (2, 0)：

   • 栈：[(0, 0), (1, 0), (2, 0)]。
   • 按顺序探索：
     • 右：可走，入栈。

4. 当前节点 (2, 1)：

   • 栈：[(0, 0), (1, 0), (2, 0), (2, 1)]。
   • 按顺序探索：
     • 右：可走，入栈。

5. 当前节点 (2, 2)：

   • 栈：[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]。
   • 按顺序探索：
     • 右：障碍。
     • 下：可走，入栈。

6. 当前节点 (3, 2)：

   • 栈：[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2)]。
   • 按顺序探索：
     • 右：障碍。
     • 下：可走，入栈。

7. 当前节点 (4, 2)：

   • 栈：[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2)]。
   • 按顺序探索：
     • 右：可走，入栈。

8. 终点 (4, 4) 入栈：

   • 栈：[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]。
   • 到达终点，结束搜索。

---

关键点详解

1. 方向状态的更新：

   • 每次移动后：
     • 当前节点的方向标记为不可走，防止重复访问。
     • 相邻节点的回头方向标记为不可走，防止回头。

2. 栈的作用：

   • 栈保存当前路径节点，用于实现深度优先搜索。
   • 当节点无法前进时，回退到上一个节点继续探索。

3. 搜索优先级：

   • 使用固定的方向顺序（右、下、左、上）确保路径唯一性。

4. 边界条件：

   • 起点或终点为障碍时，直接返回。
   • 每次移动前检查坐标是否越界。

---

时间与空间复杂度

1. 时间复杂度：

   • 每个节点最多被访问一次，复杂度为 O(n * m)，其中 n 是行数，m 是列数。

2. 空间复杂度：

   • 栈中最多存储所有节点，复杂度为 O(n * m)。

---

避免回头路的原理

1. 每个节点的方向状态：

   • 每个节点有四个方向（右、下、左、上），用一个数组 direction[4] 表示：
     • YES 表示该方向可以走。
     • NO 表示该方向不可走。

2. 双向更新：

   • 从当前节点走到相邻节点时：
     • 更新当前节点的该方向状态为 NO，表示不能再次从该方向出发。
     • 同时，更新相邻节点从回头方向来的状态为 NO，表示不能回到当前节点。

3. 目的：

   • 通过双向更新，防止程序进入重复探索（例如节点之间循环往返）。

---

实现方式

以下代码展示了如何避免回头路（取右方向为例）：

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;
}

具体步骤：

1. 检查当前节点 current 的右方向是否可走（direction[RIGHT] == YES）。
2. 检查相邻节点（右边节点）的左方向是否可走（grid[x][y + 1].direction[LEFT] == YES）。
   • 这保证了两节点之间的状态一致。
3. 更新状态：
   • 当前节点的右方向设置为 NO。
   • 右边节点的左方向设置为 NO。
   • 双向标记，确保后续无法重复走该路径。
4. 将右边节点入栈，继续探索。

---

避免回头路的完整逻辑

在四个方向（右、下、左、上）中，都应用类似逻辑。以下是完整实现：

// 右方向
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;
}

---

避免回头路的效果

1. 走过的方向：

   • 每次从一个节点走向另一个节点时，都会标记双向路径为“不可走”。
   • 例如，从 (0, 0) 走到 (0, 1) 后：
     • (0, 0) 的右方向 direction[RIGHT] 被标记为 NO。
     • (0, 1) 的左方向 direction[LEFT] 被标记为 NO。

2. 防止重复探索：

   • 在后续探索中，如果程序回退到 (0, 1)，由于其左方向 direction[LEFT] 已标记为 NO，程序不会再返回 (0, 0)。

3. 避免循环：

   • 如果没有双向标记，程序可能陷入循环（例如 (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)

1. 当前节点 (0, 0) 的 RIGHT 被设置为 NO。
2. 相邻节点 (0, 1) 的 LEFT 被设置为 NO。
3. 节点 (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)

1. 当前节点 (0, 1) 的 DOWN 被设置为 NO。
2. 相邻节点 (1, 1) 的 UP 被设置为 NO。
3. 节点 (1, 1) 入栈。

更新后的状态：

方向状态 (0, 1):
RIGHT = YES, DOWN = NO, LEFT = NO, UP = NO
方向状态 (1, 1):
RIGHT = YES, DOWN = YES, LEFT = YES, UP = NO

走到死胡同时的回退：

• 当一个节点的四个方向都不可走时，执行出栈操作，回到上一个节点。
• 回退时不会选择已标记为 NO 的方向，避免重复探索。