文章目录

• • 题单
• 一、模板 [极为重要]
• • 全排列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种选择，枚举全部则有 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 ;
    }
   //枚举前 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;
}