DFS
题单 🧑🏻💻
| 题目来源 | 题目名称 | 题目链接 | 备注 | 难度 |
|---|---|---|---|---|
| 洛谷 - P1605 | 迷宫 | 链接🔗 | DFS迷宫题 | 🟢 |
| 洛谷 - P1706 | 全排列问题 | 链接🔗 | DFS/全排列 | 🟢 |
| AtCoder - ABC 125B | Resale | 链接🔗 | DFS/贪心 | 🟢 |
| 信息学奥赛一本通 - P1212 | LETTERS | 链接🔗 | DFS | 🟡 |
| CodeForces - 1873E | Serial Time! | 链接🔗 | BFS/DFS | 🟡 |
| 洛谷 - P1120 | 小木棍 | 链接🔗 | DFS | 🟡 |
题解 🚀
全排列问题
题目信息 📚
【题目名称】洛谷 P1706 - 全排列问题
【题目描述】
按照字典序输出自然数 $1$ 到 $n$ 所有不重复的排列，即 $n$ 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
【输入】
一个整数 $n$。
【输出】
由 $1 \sim n$ 组成的所有不重复的数字序列，每行一个序列。
每个数字保留 $5$ 个场宽。
【输入样例】
3【输出样例】
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1【数据范围】
$1 \le n \le 9$。
【题目链接】
https://www.luogu.com.cn/problem/P1605
题目解析 🍉
【题目分析】
DFSの经典入门题。
关键是掌握 DFS参数的含义、「终点步」的操作、以及「普通步」的操作、标记数组的使用。
当然，本题也可以使用 STL 的 next_permutation() 函数实现。
【 C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 20;
int vis[N];
int ans[N];
int n;
// dfs：从step处开始放置数字
void dfs(int step) {
// 返回条件
if (step == n + 1) {
for (int i = 1; i <= n; i++)
cout << setw(5) << ans[i];
cout << endl;
return;
}
// 枚举数字
for (int i = 1; i <= n; i++) {
if (vis[i] == 0) {
vis[i] = 1;
ans[step] = i;
dfs(step + 1);
vis[i] = 0;
}
}
}
// 使用STL函数
void solve_stl() {
// 设定全排列的第一组(1,2,3,...n)
for (int i = 1; i <= n; i++) ans[i] = i;
// 利用next_permutation输出每一组全排列
do {
for (int i = 1; i <= n; i++)
cout << setw(5) << ans[i];
cout << endl;
} while (next_permutation(ans + 1, ans + n + 1));
}
int main() {
cin >> n;
// dfs求解（关键是理解dfs参数的含义）
dfs(1);
// 使用STL函数next_permutation()求解
// solve_stl();
return 0;
}迷宫
题目信息 📚
【题目名称】洛谷 P1605 - 迷宫
【题目描述】
给定一个 $N \times M$ 方格的迷宫，迷宫里有 $T$ 处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
【输入】
第一行为三个正整数 $N,M,T$，分别表示迷宫的长宽和障碍总数。
第二行为四个正整数 $SX,SY,FX,FY$，$SX,SY$ 代表起点坐标，$FX,FY$ 代表终点坐标。
接下来 $T$ 行，每行两个正整数，表示障碍点的坐标。
【输出】
输出从起点坐标到终点坐标的方案总数。
【输入样例】
2 2 1
1 1 2 2
1 2【输出样例】
1【数据范围】
对于 $100%$ 的数据，$1 \le N,M \le 5$，$1 \le T \le 10$，$1 \le SX,FX \le n$，$1 \le SY,FY \le m$。
【题目链接】
https://www.luogu.com.cn/problem/P1605
题目解析 🍉
【题目分析】
DFSの经典迷宫题
【 C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10;
char g[N][N]; // 存储迷宫
int vis[N][N]; // 访问标记数组
// 上、右、下、左
int walk[4][2] = {{-1, 0},
{0, +1},
{+1, 0},
{0, -1}};
int n, m, T;
int ans = 0;
// dfs搜索
void dfs(int sx, int sy) {
// 当前点已经是终点，方案数+1并返回
if (g[sx][sy] == 'T') {
ans++;
return;
}
// 当前点不是终点，往该点的四周扩展
for (int i = 0; i < 4; i++) {
int dx = sx + walk[i][0], dy = sy + walk[i][1];
// 若扩展点不为障碍物、未被当前路径访问、在边界内
// 则以该扩展点，进行下一层dfs
if (g[dx][dy] != '#' && vis[dx][dy] == 0 && dx >= 1 && dx <= n && dy >= 1 && dy <= m) {
vis[dx][dy] = 1; // 这三行代码，需要细细品味
dfs(dx, dy);
vis[dx][dy] = 0;
}
}
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
// 初始化迷宫
cin >> n >> m >> T;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
g[i][j] = '.';
// 插入终点坐标
int sx, sy, tx, ty;
cin >> sx >> sy >> tx >> ty;
g[tx][ty] = 'T';
// 插入障碍物
for (int i = 1; i <= T; i++) {
int x, y;
cin >> x >> y;
g[x][y] = '#';
}
// 输入起点位置，开始dfs搜索
vis[sx][sy] = 1;
dfs(sx, sy);
cout << ans << endl;
return 0;
}Resale
题目信息 📚
【题目名称】AtCoder - ABC 125B Resale
【题目描述】
There are $N$ gems. The value of the $i$-th gem is $V_i$.
You will choose some of these gems, possibly all or none, and get them.
However, you need to pay a cost of $C_i$ to get the $i$-th gem.
Let $X$ be the sum of the values of the gems obtained, and $Y$ be the sum of the costs paid.
Find the maximum possible value of $X - Y$.
【输入】
The input is given from Standard Input in the following format:
$N$
$V_1$ $V_2$ $\ldots$ $V_n$
$C_1$ $C_2$ $\ldots$ $C_n$
【输出】
Print the maximum possible value of $X - Y$.
【数据范围】
All values in the input are integers.
- $1 \leq N \leq 20$
- $1 \leq C_i, V_i \leq 50$
【输入样例1】
3
10 2 5
6 3 4【输出样例1】
5【输入样例2】
4
13 21 6 19
11 30 6 15 【输出样例2】
6【输入样例3】
1
1
50【输出样例3】
0【题目链接】
https://atcoder.jp/contests/abc125/tasks/abc125_b
题目解析 🍉
【题目分析】
由于数据范围较小，二进制枚举所有方案也就 $2^{20} \approx 10^6$ 级别，因此可以直接DFS暴搜。
当然，这题很容易和背包问题混淆起来，实际上并没有那么复杂：贪心，求 $X - Y$ 的最大值，只要当前物品的 $V_i > C_i$ 即可。
【 C++ 代码】DFS ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 60;
int n, c[N], v[N];
int res = 0;
// DFS暴搜
// step表示当前已经选到第step个物品，is_select表示是否选择第step个物品
// vsum表示当前V总和，csum表示当前C总和
void dfs(int step, int is_select, int vsum, int csum) {
if (step == 21) {
res = max(res, vsum - csum);
return;
}
dfs(step + 1, 0, vsum, csum);
dfs(step + 1, 1, vsum + v[step + 1], csum + c[step + 1]);
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
// 读入数据
cin >> n;
for (int i = 1; i <= n; i++) cin >> v[i];
for (int i = 1; i <= n; i++) cin >> c[i];
// 不选第1个物品
dfs(1, 0, 0, 0);
// 选择第1个物品
dfs(1, 1, v[1], c[1]);
cout << res << endl;
return 0;
}【C++代码】 贪心✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 60;
int n, c[N], v[N];
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
// 读入数据
cin >> n;
for (int i = 1; i <= n; i++) cin >> v[i];
for (int i = 1; i <= n; i++) cin >> c[i];
// 贪心
LL sum = 0;
for (int i = 1; i <= n; i++) {
if (v[i] > c[i]) sum += (v[i] - c[i]);
}
cout << sum << endl;
return 0;
}LETTERS
题目信息 📚
【题目名称】信息学奥赛一本通 - P1212 LETTERS
【题目描述】
给出一个 $roe×col$ 的大写字母矩阵，一开始的位置为左上角，你可以向上下左右四个方向移动，并且不能移向曾经经过的字母。问最多可以经过几个字母。
【输入】
第一行，输入字母矩阵行数 $R$ 和列数 $S$，$1≤ R,S≤20$。
接着输出 $R$ 行 $S$ 列字母矩阵。
【输出】
最多能走过的不同字母的个数。
【输入样例】
3 6
HFDFFB
AJHGDH
DGAGEH【输出样例】
6【题目链接】
http://ybt.ssoier.cn:8088/problem_show.php?pid=1212
http://noi.openjudge.cn/ch0205/156/
题目解析 🍉
【题目分析】
DFS
【 C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 25;
int r, c;
char g[N][N];
int walk[4][2] = {{-1, 0},
{+1, 0},
{0, +1},
{0, -1}};
int res = 0;
set<char> st; // set存储字符
void dfs(int s, int t) {
// 将当前字符加入set中，并且更新res
st.insert(g[s][t]);
if (st.size() > res) res = st.size();
// 根据该点进行拓展
for (int i = 0; i < 4; i++) {
// 拓展点坐标
int dx = s + walk[i][0], dy = t + walk[i][1];
// 该拓展点超出边界
if (dx < 1 || dx > r || dy < 1 || dy > c) continue;
// 该拓展点在边界内，且该点字符未被访问
if (find(st.begin(), st.end(), g[dx][dy]) == st.end()) {
st.insert(g[dx][dy]);
dfs(dx, dy);
st.erase(g[dx][dy]);
}
}
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> r >> c;
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
cin >> g[i][j];
dfs(1, 1);
cout << res << endl;
return 0;
}Serial Time!
题目信息 📚
【题目名称】CodeForces 60B - Serial Time!
【题目描述】
The Cereal Guy’s friend Serial Guy likes to watch soap operas. An episode is about to start, and he hasn’t washed his plate yet. But he decided to at least put in under the tap to be filled with water. The plate can be represented by a parallelepiped $k ×n×m$, that is, it has $k$ layers (the first layer is the upper one), each of which is a rectangle $n × m$ with empty squares (‘.’) and obstacles (‘#’). The water can only be present in the empty squares. The tap is positioned above the square $(x, y)$ of the first layer, it is guaranteed that this square is empty. Every minute a cubical unit of water falls into the plate. Find out in how many minutes the Serial Guy should unglue himself from the soap opera and turn the water off for it not to overfill the plate. That is, you should find the moment of time when the plate is absolutely full and is going to be overfilled in the next moment.
Note: the water fills all the area within reach (see sample 4). Water flows in each of the $6$ directions, through faces of $1 × 1 × 1$ cubes.
【输入】
The first line contains three numbers $k, n, m (1 \le k, n, m \le 10)$ which are the sizes of the plate. Then follow $k$ rectangles consisting of $n$ lines each containing $m$ characters ‘.’ or ‘#’, which represents the “layers” of the plate in the order from the top to the bottom. The rectangles are separated by empty lines (see the samples). The last line contains $x$ and $y$ $(1 \le x \le n, 1 \le y \le m)$ which are the tap’s coordinates. $x$ is the number of the line and $y$ is the number of the column. Lines of each layer are numbered from left to right by the integers from $1$ to $n$, columns of each layer are numbered from top to bottom by the integers from $1$ to $m$.
【输出】
The answer should contain a single number, showing in how many minutes the plate will be filled.
【输入样例1】
1 1 1
.
1 1【输出样例1】
1【输入样例2】
2 1 1
.
#
1 1【输出样例2】
1【输入样例3】
2 2 2
.#
##
..
..
1 1【输出样例3】
5【输入样例4】
3 3 3
.#.
###
##.
.##
###
##.
...
...
...
1 1【输出样例4】
13【题目链接】
https://codeforces.com/problemset/problem/60/B
题目解析 🍉
【题目分析】
该题本质是在三维迷宫内，求包含起点的连通块点个数，BFS和DFS均可（DFS需要在数据范围较小的情况下使用）
【 C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 15;
typedef struct node { // 定义一个三维点坐标
int x, y, z;
} node;
int walk[6][3] = {{+1, 0, 0}, // 水流的六个方向
{-1, 0, 0},
{0, +1, 0},
{0, -1, 0},
{0, 0, +1},
{0, 0, -1}};
char g[N][N][N]; // 盘子（三维迷宫）
int d[N][N][N]; // 每个格子被浇灌的时间（三维距离数组）
int k, n, m, timer;
// bfs搜索
void bfs(int sx, int sy, int sz) {
// 初始化队列和距离数组
queue<node> q;
memset(d, -1, sizeof(d));
// 加入起点，并且开始计时
q.push({sx, sy, sz});
d[sx][sy][sz] = 1;
timer = 1;
while (!q.empty()) {
// 取出队首元素，并且弹出
int x = q.front().x, y = q.front().y, z = q.front().z;
q.pop();
// 往六个方向拓展
for (int i = 0; i < 6; i++) {
int dx = x + walk[i][0], dy = y + walk[i][1], dz = z + walk[i][2];
// 越界
if (dx < 1 || dx > k || dy < 1 || dy > n || dz < 1 || dz > m) continue;
// 障碍物
if (g[dx][dy][dz] == '#') continue;
// 已经被访问过
if (d[dx][dy][dz] != -1) continue;
// 加入满足条件的拓展点，并更新时间
q.push({dx, dy, dz});
d[dx][dy][dz] = ++timer;
}
}
cout << timer << endl;
}
int ans = 0;
// dfs搜索
void dfs(int sx, int sy, int sz) {
if (sx < 1 || sx > k || sy < 1 || sy > n || sz < 1 || sz > m || g[sx][sy][sz] == '#')
return;
ans++;
g[sx][sy][sz] = '#';
for (int i = 0; i < 6; i++) {
dfs(sx + walk[i][0], sy + walk[i][1], sz + walk[i][2]);
}
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
// 读入三维迷宫
cin >> k >> n >> m;
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= n; ++j) {
for (int l = 1; l <= m; ++l) {
cin >> g[i][j][l];
}
}
}
// 输入灌水起点
int sx = 1, sy, sz;
cin >> sy >> sz;
// bfs统计包含起点的连通块总点数
// bfs(sx, sy, sz);
// dfs统计包含起点的连通块总点数
dfs(sx, sy, sz);
cout << ans << endl;
return 0;
}小木棍
题目信息 📚
【题目名称】洛谷 P1120 - 小木棍
【题目描述】
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 $50$。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
【输入】
第一行是一个整数 $n$，表示小木棍的个数。
第二行有 $n$ 个整数，表示各个木棍的长度 $a_i$。
【输出】
输出一行一个整数表示答案。
【输入样例】
9
5 2 1 5 2 1 5 2 1【输出样例】
6【数据范围】
对于全部测试点，$1 \leq n \leq 65$，$1 \leq a_i \leq 50$。
【题目链接】
https://www.luogu.com.cn/problem/P1120
题目解析 🍉
【题目分析】
题目模型可以抽象为：给定一个数组 $a$，一个数 $x$，问能否将数组a划分为几个区块，使得每个块的元素和为 $x$
【 C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100;
int n, a[N];
bool check(int x) {
if (x <= *max_element(a + 1, a + n + 1)) return false;
cout << x << endl;
int i = 1, j = n;
while (i < j) {
if (a[j] == x) {
j--;
} else if (a[j] + a[i] == x) {
j--, i++;
} else if (a[j] + a[i] < x) {
int sum = a[j] + a[i];
j--, i++;
while (sum < x) {
sum += a[i++];
}
if (sum > x) {
return false;
}
} else if (a[j] + a[i] > x) {
return false;
}
}
return true;
}
int main() {
cin >> n;
int sum = 0, maxl = -1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
maxl = max(maxl, a[i]);
sum += a[i];
}
sort(a + 1, a + n + 1);
cout << "sum: " << sum << endl;
for (int i = 1; i <= n; ++i) {
cout << a[i] << " ";
}
cout << endl;
int ans, x;
for (int i = 1; i < n; i++) {
if (sum % i == 0 && check(sum / i)) {
ans = sum / i;
}
}
cout << ans << endl;
return 0;
}
