一、回顾

深度优先搜索（Depth First Search, DFS） 是一种穷举的思想，通过递归来遍历所有可能的情况分支。对每一个可能的分支路径都会优先深入到不能再深入为止，而且每个节点只能访问一次。

所以在进行深度优先搜索时，我们需要标记已经访问过的节点，以确保不会重复访问。

“一直向前走，碰壁才回头”

结束条件：已访问过所有节点

---

二、迷宫的相邻点（四联通 => 方向数组dirx, diry引入）

题目描述

一个迷宫由 n 行 m 列格子组成，给定其中的一个位置坐标 (x, y)，求出其上下左右相邻点的坐标。注意：输出时按照右下左上的方向输出。

输入格式

输入仅一行，包含 4 个整数 n, m, x, y。约束条件：0 < n, m ≤ 1000; 1 ≤ x ≤ n, 1 ≤ y ≤ m

输出格式

输出有 4 行，按照右下左上的方向输出 (x, y) 这个点的 4 个相邻点。每一行输出两个数，分别包含行坐标和列坐标，其间用一个空格隔开。注意：如果其中某个相邻点越界了则输出 NA。

样例组输入 #1

5 6 2 1

样例组输出 #1

2 2
3 1
NA
1 1

解题思路

1. 方向顺序：按题目要求的顺序，依次检查右、下、左、上四个方向。
2. 坐标计算：
   • 右：(x, y+1)
   • 下：(x+1, y)
   • 左：(x, y-1)
   • 上：(x-1, y)
3. 边界判断：新坐标的行必须在 [1, n] 之间，列必须在 [1, m] 之间，否则输出 NA

标程

#include <bits/stdc++.h>  // 万能头文件，包含C++所有常用库
using namespace std;    // 使用标准命名空间，省去每次写std::

// 方向数组：下标 1~4 分别对应 右、下、左、上 四个方向
// 下标0不用，方便从1开始遍历方向
int dx[]={0, 0, 1, 0, -1};  // dx[i]：行坐标的变化量
int dy[]={0, 1, 0, -1, 0};  // dy[i]：列坐标的变化量
// 方向对应关系：
// i=1 → 右 (dx=0, dy=1)
// i=2 → 下 (dx=1, dy=0)
// i=3 → 左 (dx=0, dy=-1)
// i=4 → 上 (dx=-1, dy=0)
// 正好满足题目要求：按 右下左上 顺序输出

int main() {
    int n, m, x, y;          // n行m列的迷宫，当前点坐标(x,y)
    cin >> n >> m >> x >> y; // 输入四个整数

    // 循环遍历4个方向（右、下、左、上）
    for(int i=1;i<=4;i++) {
        // 判断 新坐标 是否在迷宫范围内（不越界）
        if((x+dx[i])<=n && (x+dx[i])>0 &&    // 新行在1~n之间
           (y+dy[i])<=m && (y+dy[i]>0))      // 新列在1~m之间
        {
            // 不越界：输出相邻点坐标
            cout << (x+dx[i]) << ' ' << (y+dy[i]) << endl;
        }
        else {
            // 越界：输出NA
            puts("NA");
        }
    }

    return 0; // 程序正常结束
}

代码核心总结

1. 方向数组：用 dx/dy 统一管理上下左右，代码更简洁
2. 遍历顺序：i=1~4 正好是题目要求的 右 → 下 → 左 → 上
3. 边界判断：确保坐标在 1~n 行、1~m 列之间，否则输出 NA

三、迷宫之判定（实战~）

【题目描述】

一个迷宫由 n 行 m 列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。给定一个迷宫，求从左上角走到右下角是否能走通。

【输入格式】

第一行是两个整数 n 和 m，代表迷宫的长和宽。（1 ≤ n, m ≤ 40）接下来是 n 行，每行 m 个字符，代表整个迷宫。空地格子用 0 表示，有障碍物的格子用 1 表示。确保迷宫左上角和右下角都是 0。

【输出格式】

输出能否从左上角走到右下角，如果可以输出 "YES"，若走不通，输出 "NO"。输出的内容不包含双引号。

【输入样例】

5 5
00111
10000
10101
10101
10100

【输出样例】

YES

解题思路

这道题可以用 DFS（深度优先搜索） 来解决，和你之前学的思路完全对应：

1. 从起点 (0,0)（或 (1,1)，看你数组下标习惯）出发，用方向数组尝试上下左右四个方向。
2. 每次移动前，判断新坐标是否：
   • 在迷宫范围内
   • 不是障碍物（值为 0）
   • 没有被访问过（防止走回头路、死循环）
3. 如果能走到终点 (n-1, m-1)，说明有通路，返回 YES；如果所有路径都走不通，返回 NO。

标程

#include <bits/stdc++.h>  // 万能头文件，包含C++所有常用库
using namespace std;    // 使用标准命名空间

// 方向数组：下标 1~4 对应 右、下、左、上
int dx[]={0, 0, 1, 0, -1};  // 行坐标变化量
int dy[]={0, 1, 0, -1, 0};  // 列坐标变化量
// 方向对应：
// i=1 → 右
// i=2 → 下
// i=3 → 左
// i=4 → 上

bool tu[41][41];        // 存储迷宫地图：0=可走，1=障碍
bool vis[41][41]={0};   // 标记是否访问过，防止重复走
bool flag=false;        // 标记是否找到终点：true=找到，false=没找到
int n, m;               // 迷宫的行数n，列数m

// DFS 深度优先搜索函数
// 当前位置 (x, y)
void dfs(int x, int y) {
    // 递归出口：如果走到了右下角终点 (n,m)
    if(x == n && y == m) {
        flag = true;   // 标记找到通路
        return;        // 结束当前递归
    }

    // 遍历四个方向：右、下、左、上
    for(int i=1; i<=4; i++) {
        // 计算下一步的坐标
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 判断条件：
        // 1. 新坐标在迷宫内（不越界）
        // 2. 不是障碍物 tu[nx][ny] == 0
        // 3. 没有被访问过 vis[nx][ny] == 0
        if( nx >= 1 && nx <= n &&
            ny >= 1 && ny <= m &&
            !tu[nx][ny] && !vis[nx][ny] )
        {
            vis[nx][ny] = true;   // 标记这个点已经走过
            dfs(nx, ny);          // 递归继续走下一步
        }
    }
}

int main() {
    cin >> n >> m;  // 输入迷宫行数和列数

    // 输入迷宫地图
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >> tu[i][j];

    vis[1][1] = 1; // 标记起点走过
    dfs(1, 1);  // 从左上角起点 (1,1) 开始搜索

    // 根据 flag 输出结果
    if(flag)
        puts("YES");  // 能走到终点
    else
        puts("NO");   // 走不到终点

    return 0;
}

代码说明

• 方向数组和你之前写的格式完全兼容，只是顺序改成了上下左右，不影响结果。
• vis 数组是 DFS 的关键，避免了 “走回头路” 导致的死循环。
• 递归的出口直接判断是否到达终点，只要有一条路径能走到，就会一路返回 true。

💡 给你的小建议

以后写 DFS 迷宫题，记住这几个固定检查点：

1. 起点必须提前标记 vis，防止回头走
2. 行、列的边界判断别写反
3. 找到终点后及时 return，避免做无用的搜索
4. 遇到死胡同不用手动回溯，递归自然返回就好

---

三、迷宫之方案数（回溯引入）

【题目描述】

给定一个 N×M 方格的迷宫，迷宫里有 T 处障碍，障碍处不可通过。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

【输入格式】

1. 第一行为三个正整数 N, M, T，分别表示迷宫的长宽和障碍总数。
2. 第二行为四个正整数 SX, SY, FX, FY，SX, SY 代表起点坐标，FX, FY 代表终点坐标。
3. 接下来 T 行，每行两个正整数，表示障碍点的坐标。

【输出格式】

输出从起点坐标到终点坐标的方案总数。

【输入样例 1】

2 2 1
1 1 2 2
1 2

【输出样例 1】1

【输入样例 2】

3 3 1
1 1 3 3
1 2

【输出样例 2】4

【数据范围】

对于 100% 的数据：1 ≤ N, M ≤ 5，1 ≤ T ≤ 10，1 ≤ SX, FX ≤ n，1 ≤ SY, FY ≤ m。

解题思路

这道题和你之前写的迷宫判定题是 “升级版”：

1. 核心还是 DFS 深度优先搜索，但这次不是判断 “能不能走通”，而是统计 “所有能走通的路径数量”。
2. 关键变化：
   • 找到终点时，计数器 ans++，而不是直接返回 true。
   • 为了统计所有路径，必须用到回溯：走完一条分支后，要把 vis 标记清除，让其他分支也能走这个格子。
3. 边界条件：坐标不越界、不是障碍、没访问过。

#include <bits/stdc++.h>
using namespace std;

// 方向数组：下标1~4对应 右、下、左、上，和你之前的习惯一致
int dx[] = {0, 0, 1, 0, -1};
int dy[] = {0, 1, 0, -1, 0};

bool tu[10][10];    // 迷宫地图：true=障碍，false=可走
bool vis[10][10];   // 访问标记：true=已走过，false=未走过
int n, m, t;        // 迷宫n行m列，t个障碍
int sx, sy, fx, fy; // 起点、终点坐标
int ans = 0;        // 方案数计数器

// DFS函数：当前在(x,y)位置
void dfs(int x, int y) {
    // 递归出口：走到终点了，方案数+1
    if (x == fx && y == fy) {
        ans++;
        return;
    }

    // 遍历四个方向
    for (int i = 1; i <= 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 边界判断 + 障碍判断 + 访问标记判断
        if (nx >= 1 && nx <= n &&    // 行不越界
            ny >= 1 && ny <= m &&    // 列不越界
            !tu[nx][ny] &&           // 不是障碍
            !vis[nx][ny])            // 没走过
        {
            vis[nx][ny] = true;      // 标记为已访问
            dfs(nx, ny);             // 递归探索下一个点
            vis[nx][ny] = false;     // 回溯：清除标记，让其他路径可以走这里
        }
    }
}

int main() {
    cin >> n >> m >> t;
    cin >> sx >> sy >> fx >> fy;

    // 初始化障碍：tu数组默认是false（可走），障碍点设为true
    memset(tu, false, sizeof(tu));
    for (int i = 1; i <= t; i++) {
        int x, y;
        cin >> x >> y;
        tu[x][y] = true;
    }

    // 起点标记为已访问，防止回头走
    vis[sx][sy] = true;
    dfs(sx, sy);

    cout << ans << endl;
    return 0;
}

代码关键点说明

1. 回溯操作 vis[nx][ny] = false：这是和 “判定是否能走通” 的代码最大的区别。如果不清除标记，第一次走过的路径会把所有格子都锁死，后面的路径就没法探索了。
2. 方向数组和边界判断：完全沿用了你之前写的风格，行 x 对应 n，列 y 对应 m，不会再写反啦。
3. 数据范围适配：因为题目里 n,m≤5，所以数组开 10×10 完全够用，不用考虑空间问题。