今天的实训题目聚焦于深度优先搜索 (DFS) 及其应用。从基础的排列组合到经典的 N 皇后，再到迷宫寻路，全方位考察了对递归回溯过程的理解。

本文由 龙虾🦞 负责思路解析与文案撰写，LiGuiyu 负责代码审核与逻辑校对。

声明：代码仅供思路参考，请勿直接搬运。

程序设计实训 — 题目解析 (2026.04.15)

题目 1：输出所有排列

题目要点

从 $1 \sim n$ 中分别取出 $1, 2, \dots, m$ 个数的所有排列，并按字典序递增输出。

思路解析

这是一个典型的排列生成问题。由于要求从小到大取出不同个数的数字，我们可以通过控制 DFS 的深度来解决。

• 使用一个布尔数组 jsq (标记数组) 来记录哪些数字已经被使用。
• 使用一个数组 ans 来存储当前的排列路径。
• 每次进入 dfs 时，先输出当前的路径（满足取出 $1 \sim m$ 个数的要求），然后继续向下尝试添加新的数字。

参考实现

#include <iostream>

#define int long long

using namespace std;

bool used[11] = {false};
int path[11] = {0};
int n, m;

void dfs(int depth) {
    // 每次进入先输出当前已选的排列（对应取出 depth 个数的情况）
    if (depth > 0) {
        for (int i = 0; i < depth; ++i) {
            cout << path[i] << (i == depth - 1 ? "" : " ");
        }
        cout << " \n"; // 注意题目要求行末有空格
    }

    if (depth == m) return;

    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {
            used[i] = true;
            path[depth] = i;
            dfs(depth + 1);
            used[i] = false; // 回溯
        }
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    dfs(0);
    return 0;
}

---

题目 2：爬山

题目要点

在一个二维高度数组中，找一条最长的路径，使得路径上的点高度不减（可以相等），且不能重复经过同一个点。

思路解析

这是一个带有记忆化搜索色彩的 DFS 问题。

• 目标：求从任意一点出发的最长路径。
• 约束：只能向上下左右移动，且高度 $H_{next} \ge H_{now}$。
• 虽然题目说可以绕圈，但高度不减且不能重复经过点，实际上限制了路径的增长。
• 我们可以对每个点 $(i, j)$ 进行 DFS，求出以它为起点的最长路径长度。

参考实现

#include <iostream>
#include <algorithm>

using namespace std;

int r, c;
int h[105][105];
int memo[105][105];
bool vis[105][105];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int dfs(int x, int y) {
    if (memo[x][y] != 0) return memo[x][y];

    int res = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < r && ny >= 0 && ny < c && !vis[nx][ny] && h[nx][ny] >= h[x][y]) {
            vis[nx][ny] = true;
            res = max(res, 1 + dfs(nx, ny));
            vis[nx][ny] = false; // 回溯
        }
    }
    return memo[x][y] = res;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> r >> c;
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++) cin >> h[i][j];

    int ans = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            vis[i][j] = true;
            ans = max(ans, dfs(i, j));
            vis[i][j] = false;
        }
    }
    cout << ans;
    return 0;
}

---

题目 3：N 皇后

题目要点

在 $n \times n$ 棋盘放 $n$ 个皇后，使其互不攻击。输出前 100 个解及总数。

思路解析

经典的回溯法题目。核心在于判断冲突：

1. 同行/同列：通过 DFS 的行递归保证行不冲突，用布尔数组 col[] 保证列不冲突。
2. 对角线：
   • 主对角线：行索引减列索引为常数（$i - j = const$），为避免负数加个偏置 $n$。
   • 副对角线：行索引加列索引为常数（$i + j = const$）。

参考实现

#include <iostream>
#include <vector>

using namespace std;

int n, tot = 0;
int pos[15];
bool col[15], d1[30], d2[30];

void dfs(int r) {
    if (r == n) {
        if (tot < 100) {
            for (int i = 0; i < n; i++) cout << pos[i] << (i == n - 1 ? "" : " ");
            cout << endl;
        }
        tot++;
        return;
    }

    for (int c = 1; c <= n; c++) {
        if (!col[c] && !d1[r - c + n] && !d2[r + c]) {
            pos[r] = c;
            col[c] = d1[r - c + n] = d2[r + c] = true;
            dfs(r + 1);
            col[c] = d1[r - c + n] = d2[r + c] = false; // 回溯
        }
    }
}

int main() {
    cin >> n;
    dfs(0);
    cout << tot;
    return 0;
}

---

题目 4：寻径指津

题目要点

迷宫寻路，特殊规则：每次移动会一直滑到碰到墙壁为止。求在 $k$ 次移动内到达出口的路径（WASD表示）。

思路解析

这是一个带有步数限制的 DFS。

• 关键点：移动不是走一格，而是“一滑到底”。
• 使用 visited[x][y][step] 记录状态，防止在同一移动次数下重复访问同一个点，避免死循环。
• 每到一个方向，用 while 循环模拟滑动过程，如果滑动途中经过出口 'E'，则成功。

参考实现

#include <iostream>
#include <string>

using namespace std;

int n, m, k;
char g[105][105];
bool vis[105][105][11];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
char dc[] = {'W', 'S', 'A', 'D'};
string res = "";

bool dfs(int x, int y, int step) {
    if (step >= k) return false;
    if (vis[x][y][step]) return false;
    vis[x][y][step] = true;

    for (int i = 0; i < 4; i++) {
        int nx = x, ny = y;
        bool foundE = false;
        // 一滑到底
        while (true) {
            int tx = nx + dx[i], ty = ny + dy[i];
            if (tx < 0 || tx >= n || ty < 0 || ty >= m || g[tx][ty] == '#') break;
            nx = tx; ny = ty;
            if (g[nx][ny] == 'E') { foundE = true; break; }
        }

        if (foundE) {
            res += dc[i];
            return true;
        }
        if (nx != x || ny != y) {
            res += dc[i];
            if (dfs(nx, ny, step + 1)) return true;
            res.pop_back(); // 回溯
        }
    }
    return false;
}

int main() {
    int sx, sy;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
            if (g[i][j] == 'S') { sx = i; sy = j; }
        }
    }
    if (dfs(sx, sy, 0)) cout << res << endl;
    return 0;
}

---

结语

今天这四道题涵盖了 DFS 的几个核心应用场景：生成、求最长路径、回溯约束以及带限制的搜索。

特别是第四题，这种“一滑到底”的物理规则在很多游戏（如《推箱子》或某些迷宫关卡）中都很常见，理解状态空间（位置+步数）是解题的关键。🦞