跳转至

J-L26 搜索

覆盖词条：KJ-35/回溯 ｜ 先修：J-L24/L17

全排列1

全排列

题目描述

输出 \(1 \sim n\) 的所有全排列，按字典序从小到大输出，每个排列占一行，数与数之间用空格分隔。

输入格式

一行一个整数 \(n\)。

输出格式

若干行，每行一个排列。

样例输入

1
3

样例输出

1
2
3
4
5
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

数据范围

  • \(1 \le n \le 8\)
全排列 AC 代码

解题思路

DFS 回溯：按字典序逐位枚举没用过的数，used[] 标记占用，递归返回后弹出并取消标记（恢复现场）；枚举满 \(n\) 位即输出一个排列。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> path;
vector<bool> used;

void dfs(int depth) {
    if (depth == n) {                      // 输出一个排列
        for (int i = 0; i < n; i++) cout << path[i] << " \n"[i == n - 1];
        return;
    }
    for (int v = 1; v <= n; v++) {         // 从小到大尝试，保证字典序
        if (used[v]) continue;
        used[v] = true;
        path.push_back(v);
        dfs(depth + 1);
        path.pop_back();                   // 恢复现场
        used[v] = false;
    }
}

int main() {
    cin >> n;
    used.assign(n + 1, false);
    dfs(0);
    return 0;
}

马的遍历2

马的遍历

题目描述

\(n \times m\) 的棋盘上有一匹马，从 \((sx, sy)\) 出发，按「日」字跳跃。求马到达棋盘每个格子的最少步数；无法到达的格子输出 -1。起点步数为 0。

输入格式

一行四个整数 \(n, m, sx, sy\)。

输出格式

\(n\) 行 \(m\) 列，第 \(i\) 行第 \(j\) 个数为马到格子 \((i, j)\) 的最少步数，用空格分隔。

样例输入

1
3 3 1 1

样例输出

1
2
3
0 3 2
3 -1 1
2 1 4

数据范围

  • \(1 \le n, m \le 400\)
  • \(1 \le sx \le n\)，\(1 \le sy \le m\)
马的遍历 AC 代码

解题思路

BFS 求最短路：马跳一步相当于图上走一条边，队列按层扩展，第一次到达某格时的步数就是最少步数；入队时立刻标记，防止重复入队。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, sx, sy;
    cin >> n >> m >> sx >> sy;
    vector<vector<int>> step(n + 1, vector<int>(m + 1, -1));
    int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
    int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};
    queue<pair<int, int>> q;
    q.push({sx, sy});
    step[sx][sy] = 0;                      // 起点入队时标记，防止重复入队
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 8; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > n || ny < 1 || ny > m || step[nx][ny] != -1) continue;
            step[nx][ny] = step[x][y] + 1;
            q.push({nx, ny});
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cout << step[i][j] << " \n"[j == m];
    return 0;
}

细胞计数3

细胞计数

题目描述

一个 \(n \times m\) 的 01 矩阵，1 表示细胞、0 表示空地。两个 1 只要上下左右相邻（四连通）就属于同一个细胞。求矩阵中细胞的个数。

输入格式

第一行两个整数 \(n, m\)；接下来 \(n\) 行，每行一个长度为 \(m\) 的 01 串（无空格）。

输出格式

一行一个整数，细胞个数。

样例输入

1
2
3
4
5
4 5
11000
11001
00100
00011

样例输出

1
4

数据范围

  • \(1 \le n, m \le 100\)
细胞计数 AC 代码

解题思路

Flood Fill：外层扫描矩阵，遇到未被清除的 1 说明发现一个新细胞，计数加一，并从它出发 DFS 把整个四连通块清零，避免重复统计。

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<string> g;

// 泛洪：把与 (x,y) 四连通的整个细胞抹成 0
void fill(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '1') return;
    g[x][y] = '0';
    fill(x + 1, y);
    fill(x - 1, y);
    fill(x, y + 1);
    fill(x, y - 1);
}

int main() {
    cin >> n >> m;
    g.resize(n);
    for (auto& s : g) cin >> s;
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '1') {
                cnt++;                     // 发现新连通块
                fill(i, j);
            }
    cout << cnt << "\n";
    return 0;
}

模板与代码（待补充）

  • 子集枚举（选/不选，\(2^n\) 种）
  • 组合 C(n,k)（start 参数防重复）
  • 八皇后（列 + 主副对角线标记）
  • 迷宫最短路（网格 BFS 方向数组模板）

  1. DFS 回溯 · 洛谷 P1706。 ↩

  2. BFS 最短路 · 洛谷 P1443。 ↩

  3. Flood Fill 四连通 · 同类题洛谷 P1451。 ↩