2024年CSP-J暑假冲刺训练营(8)：DFS/BFS

一、DFS

1. 意义：$n$ 重循环
2. 范围：$n\le 16$
3. 特点：有选择范围、时间复杂度高
4. 类型：
   • 求所有情况
   • 枚举判断类型
   • 不可重用类型

二、BFS

1. 意义：类似"树"的工作原理
2. 范围：$n\le 10000$
3. 特点：最短路、空间复杂度高
4. 类型：最短路模板

三、模板

1. 整数拆分

#include <bits/stdc++.h>
using namespace std;int n, a[55];void dfs(int step, int x, int last) {if (x == 0) {printf("%d=%d", n, a[1]);for (int i = 2; i <= step-1; i++) {printf("+%d", a[i]);}printf("\n");return;}for (int i = min(last, x); i >= 1; i--) {a[step] = i;dfs(step+1, x-i, i);}
}int main() {cin >> n;dfs(1, n, 1e8);return 0;
}

2. n 皇后

#include <iostream>
#include <cstdio>
using namespace std;int n, cnt, a[20], vc[20], vl[40], vr[40];void dfs(int step) {if (step == n+1) {cnt++;if (cnt <= 3) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++)if (j == a[i]) cout << "q";else cout << "~";cout << endl;}cout << endl;}return;}for (int j = 1; j <= n; j++) {if (!vc[j] && !vl[step-j+n] && !vr[step+j]) {a[step] = j;vc[j] = 1, vl[step-j+n] = 1, vr[step+j] = 1;dfs(step+1);vc[j] = 0, vl[step-j+n] = 0, vr[step+j] = 0;}}
}int main() {cin >> n;dfs(1);cout << cnt;return 0;
}

3. 最短路

#include <iostream>
#include <queue>
using namespace std;struct Node {int x, y, step;
};int n;
int a[110][110];
int vis[110][110];
int x1, y1, x2, y2;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};queue <Node> q;void bfs() {q.push({x1, y1, 0});vis[x1][y1] = 1;while (!q.empty()) {auto [fx, fy, fstep] = q.front();q.pop();if (fx == x2 && fy == y2) {cout << fstep;return;}for (int i = 0; i < 4; i++) {int tx = fx + dx[i];int ty = fy + dy[i];if (tx >= 1 && tx <= n && ty >= 1 && ty <= n && !vis[tx][ty] && !a[tx][ty]) {vis[tx][ty] = 1;q.push({tx, ty, fstep+1});}}}
}int main() {cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> a[i][j];cin >> x1 >> y1 >> x2 >> y2;bfs();return 0;
}

三、例题

1. [蓝桥杯 2016 国 AC] 路径之谜

#include <iostream>
#include <vector>
using namespace std;int n, len;
int vis[40][40];
int rs[40], cs[40];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
vector <int> path;void dfs(int x, int y) {if (x == n && y == n && len == 0) {for (auto v : path) {cout << v << " ";}return;}for (int i = 0; i < 4; i++) {int tx = x + dx[i];int ty = y + dy[i];if (vis[tx][ty] || rs[tx] == 0 || cs[ty] == 0) continue;path.push_back((tx-1)*n+ty-1);vis[tx][ty] = 1, rs[tx]--, cs[ty]--, len--;dfs(tx, ty);vis[tx][ty] = 0, rs[tx]++, cs[ty]++, len++;path.pop_back();}
}int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> cs[i];len += cs[i];vis[0][i] = vis[n+1][i] = 1;}for (int i = 1; i <= n; i++) {cin >> rs[i];vis[i][0] = vis[i][n+1] = 1;}path.push_back(0);vis[1][1] = 1, rs[1]--, cs[1]--, len--;dfs(1, 1);return 0;
}