DFS 迷宫问题课堂笔记

一、DFS 核心思想

深度优先搜索（DFS）的核心是 “一条路走到黑”：从起点出发，沿一个方向持续探索，直到无法继续（碰壁、越界或已访问），再回溯尝试其他路径。

关键洞察：迷宫可达性问题中，同一格子最多访问一次（通过 vis 数组标记），避免重复探索与死循环。

二、代码结构通用模板

两段代码均遵循以下框架，可作为 DFS 迷宫问题的通用解法：

1. 全局变量定义

2. 方向数组设计

通过方向数组快速生成四个方向的新坐标，两段代码仅索引起始不同：

• 代码1（1-based 索引）：

  int dx[5] = {0,-1, 0, 1, 0}; // 行变化：上、右、下、左（索引1-4）
  int dy[5] = {0, 0, 1, 0,-1}; // 列变化：上、右、下、左（索引1-4）
  

• 代码2（0-based 索引）：

  int dx[4] = {-1,0,1,0}; // 行变化：上、右、下、左（索引0-3）
  int dy[4] = {0,1,0,-1}; // 列变化：上、右、下、左（索引0-3）
  

3. DFS 函数逻辑

void dfs(int x, int y) {
    // 遍历四个方向
    for (int i = 起始索引; i <= 结束索引; i++) {
        int newx = x + dx[i], newy = y + dy[i]; // 生成新坐标
        // 检查三个条件：
        // 1. 新坐标在迷宫范围内（边界检查）
        // 2. 新坐标未被访问（vis[newx][newy] == 0）
        // 3. 新坐标不是障碍物（a[newx][newy] == 0 或 c[newx][newy] != '#'）
        if (条件1 && 条件2 && 条件3) {
            vis[newx][newy] = 1; // 标记为已访问
            dfs(newx, newy);      // 递归探索新坐标
        }
    }
}

4. 主函数流程

1. 输入迷宫尺寸：cin >> n（或 n >> m）
2. 输入迷宫数据：
   • 代码1：直接输入整数数组 a[i][j]
   • 代码2：输入字符数组 c[i][j]，同时识别起点 's' 和终点 'g'
3. 特殊情况判断（代码1）：若起点或终点是障碍物，直接输出 "NO"
4. 初始化起点：标记 vis[startx][starty] = 1，并调用 dfs(startx, starty)
5. 结果判断：若 vis[endx][endy] == 1，说明终点可达，输出 "YES"（或 "Yes"）；否则输出 "NO"（或 "No"）

三、关键知识点总结

1. 方向数组的妙用

通过 dx 和 dy 数组量化四个方向的坐标变化，避免重复写四个 if 语句，代码更简洁。

2. vis 数组的作用

• 防止重复访问同一格子（避免死循环）
• 记录已探索区域，最终通过 vis[终点] 判断是否可达

3. 边界检查的重要性

必须确保新坐标 (newx, newy) 在迷宫范围内（如 1 ≤ newx ≤ n），否则会导致数组越界错误。