【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种选择，枚举全部则有 3¹⁰ 种方案数
  
  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 ;}//枚举前 1000for(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; // 如果没选就不计算resint 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/