文章目录
题单 一、模板 [极为重要]全排列DFS组合型DFS指数DFS 二、专题烤鸡 (指数BFS）P1088 火星人 【全排列】P1149 火彩棒 [预处理 ]P2036 PERKETP1135 奇怪的电梯 暴力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
#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
#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
#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/
小猫爬山
题目链接
#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 40;int c[N], cab[N], n , w, ans ;bool cmp (int a, int b){ return a > b;}void dfs(int u, int cnt) { if(cnt >= ans) return ; if(u == n + 1) { // 遍历完每只小猫后 更新答案 ！ ans = min (ans, cnt); return; } for(int i = 1; i <= cnt; i ++) { // 遍历已经分配的车子 看看有没有合适的 if(c[u] + cab[i] <= w) { cab[i] += c[u]; dfs(u + 1, cnt); cab[i] -= c[u]; } } cab[cnt + 1] = c[u]; // 没有合适的情况 就需要多加一个车子 dfs(u + 1, cnt + 1); cab[cnt + 1] = 0; }int main () { cin >> n >> w; for(int i = 1; i <= n; i ++) cin >> c[i]; ans = n; sort(c + 1, c + 1 + n, cmp); dfs(1, 1); cout << ans << endl; return 0;}