文章目录
- 题单
- 一、模板 [极为重要]
- 全排列DFS
- 组合型DFS
- 指数DFS
- 二、专题
- 烤鸡 (指数BFS）
- P1088 火星人 【全排列】
- P1149 火彩棒 [预处理 ]
- P2036 PERKET
- P1135 奇怪的电梯 暴力
- P1036 [NOIP2002 普及组] 选数 （组合）
- P1596 [USACO10OCT]Lake Counting S 【DFS求图的连通块】
- 八数码
【DFS专题】优质题单推荐 10道题（C++ | 洛谷 | acwing）
题单
- 来自b站大佬的题单
一、模板 [极为重要]
全排列DFS
- 每个位置选什么数
#include<iostream>
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{
if(u > n)//数字填完了，输出
{
for(int i = 1; i <= n; i++)//输出方案
cout << path[i] << " ";
cout << endl;
}
for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n
{
if(!state[i])//如果数字 i 没有被用过
{
path[u] = i;//放入空位
state[i] = 1;//数字被用，修改状态
dfs(u + 1);//填下一个位
state[i] = 0;//回溯，取出 i
}
}
}
int main() {
cin >> n;
dfs(1);
}
组合型DFS
- 与全排列的差别就是第二个for循环开始的位置，换句话说就是每个数该放什么位置。
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int path[N];
int n, m;
void dfs (int u, int start ) {//u:层数 start：起始的数值
if (u > m) {
for (int i = 1; i <= m; i ++ ) {
cout << path[i] << ' ';
}
puts("");
}
else {
for (int i = start; i <= n; i ++) {//
path[u] = i;//表示已经填了
dfs(u + 1, i + 1);//递归下一层
path[u] = 0;//恢复现场
}
}
}
int main () {
cin >> n >> m;
dfs(1,1); //第一层开始 且从1开始枚举
return 0;
}
指数DFS
- 参数 ： 前u个数 选 or 不选 的
- 需要保存第x位置的状态的时候就需要用st数组来存状态
- int st[] 0：没有遇见 1 选 2不选
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 16;
int st[N];
int n;
void dfs (int u) {//u ：层数
if (u > n) {//叶子结点
for (int i = 1; i <=n; i ++ ){
if (st[i] == 1) {//如果选了 就输出 1选 2不选
cout << i << ' ';
}
}
puts("");
return ;
}
st [u] = 1;//选
dfs (u + 1);//递归下一层
st[u] = 0;//回溯
st[u] = 2;//不选
dfs (u+1);//递归下一层
st[u] = 0;//回溯 【恢复现场】
}
int main () {
cin >> n;
dfs(1);
return 0;
}
二、专题
烤鸡 (指数BFS）
- 每个方案有3种选择，枚举全部则有 310 种方案数
https://www.luogu.com.cn/problem/P2089
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int n;
int arr[N]; // 存储临时答案
int res = 0;// 方案数量
int mem[60000][N]; // 存储总方案数
// 60000 >= 3^10 (最多枚举数量)
// x : 当前枚举到哪个数 sum : 当前总和
void dfs(int x, int sum ) {
if(sum > n) return ;// 剪枝
if(x > 10) {
if(sum == n) {
res ++;
for(int i = 1; i <= 10; i ++) {
mem[res][i] = arr[i];
}
}
return;
}
for(int i = 1; i <= 3; i ++) {
arr[x] = i;
dfs(x + 1, sum + i);
arr[x] = 0; // 恢复现场
}
}
int main () {
cin >> n;
dfs(1, 0);
printf("%d\n" , res);
for (int i = 1; i <= res; i ++ ) {
for(int j = 1; j <= 10; j ++) {
printf("%d ", mem[i][j]);
}
printf("\n");
}
return 0;
}
P1088 火星人 【全排列】
- https://www.luogu.com.cn/problem/P1088
- 为什么要 m + 1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n, m;
int res = 0;
int ans[N], a[N];
bool st[N];
bool flag = false;
void dfs(int x) {
if(flag) return; //剪枝 因为只会输出一次结果
if(x > n) {
res ++;
if(res == m + 1) {
for(int i = 1; i <= n; i ++ ){
printf("%d ", ans[i]);
}
flag =true;
}
return ;
}
for (int i = 1; i <= n; i ++ ){
if(!res) {
i = a[x]; // 起点
}
if(! st[i]) {
st[i] = true;
ans[x] = i;
dfs(x + 1);
ans[x] = 0;
st[i] = false;
}
}
}
int main () {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);;
dfs(1);
return 0;
}
P1149 火彩棒 [预处理 ]
https://www.luogu.com.cn/problem/P1149
- 思路一 、 模拟
- 思路二 ：预处理 + dfs 枚举
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int res = 0;
int s[N];
int num[N] = {6,2,5,5,4,5,6,3,7,6};
void dfs(int x, int sum) {
if(sum > n ) return ;
if(x > 3) {
if(s[1] + s[2] == s[3] && sum == n) {
res ++;
}
return ;
}
//枚举前 1000
for(int i = 0; i <= 1000; i ++) {
s[x] = i;
dfs(x + 1, sum + num[i]) ;
s[x] = 0;
}
}
int main () {
scanf("%d", &n);
n -= 4;
//递推求前1000个数
for (int i = 10; i <= 1000; i ++ ) {
num[i] = num[i % 10] + num[i / 10];
}
dfs(1, 0);
printf("%d\n" , res);
return 0;
}
P2036 PERKET
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int n;
int res = 1e9;
int s[N], k[N];
int st[N]; // 0 表示没考虑 1 选 2 不选
void dfs(int x) {
if(x > n) {
bool first = false; // 如果没选就不计算res
int sum1 = 1;//酸的积
int sum2 = 0; // 苦的和
for (int i = 1; i <= n; i ++ ) {
if(st[i] == 1) {
sum1 *= s[i];
sum2 += k[i];
first = true;
}
}
if(first) {
res = min(res, abs(sum1 - sum2));
}
return ;
}
st[x] = 1;
dfs(x + 1);
st[x] = 0;
st[x] = 2;
dfs(x + 1);
st[x] = 0;
}
int main () {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &s[i], &k[i]);;
dfs(1);
printf("%d\n" , res);
return 0;
}
P1135 奇怪的电梯 暴力
Ki 的值 表示 上 or 下 的层数
- 学个思路就可以
P1036 [NOIP2002 普及组] 选数 （组合）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
int n, k;
int a[N], q[N];
int res = 0;
//判断是否为素数
bool is_prime(int x) {
if(x < 2) return false;
for(int i = 2; i <= x / i; i ++) { // 从2开始呀
if(x % i == 0) return false;
}
return true;
}
void dfs(int x, int start) {
if(x > k) {
int sum = 0;
for(int i = 1; i <= k; i ++) {
sum += a[i];
}
if(is_prime(sum)) {
res ++;
}
return;
}
for(int i = start; i <= n; i ++) {
a[x] = q[i];
dfs(x + 1, i + 1);
a[x] = 0;
}
}
int main () {
cin >> n >> k;
for (int i = 1; i <= n; i ++ ) cin >> q[i];
dfs(1, 1);
cout << res << endl;
return 0;
}
P1596 [USACO10OCT]Lake Counting S 【DFS求图的连通块】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
char g[N][N];
bool st[N][N];
int res = 0;
int dx[8] = {1,1,1,0,0,-1,-1,-1};
int dy[8] = {-1,0,1,1,-1,1,0,-1};
void dfs(int x, int y) {
for(int i = 0; i < 8; i ++) {
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue; // 越界
if(g[a][b] != 'W' ) continue; // 不是山
if(st[a][b]) continue; //来过
st[a][b] = true;
dfs(a, b);
}
}
int main () {
cin >> n >> m;
for(int i = 0; i < n; i ++) cin >> g[i];
for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < m; j ++ ) {
if(g[i][j] == 'W' && !st[i][j]) {
dfs(i, j);
res ++;
}
// cout << g[i][j] << ' ';
}
// cout << endl;
}
cout << res << endl;
return 0;
}
八数码
- https://www.acwing.com/problem/content/1116/ 棋盘题
tijie : https://www.acwing.com/solution/content/133704/
