【DFS专题】深度优先搜索 “暴搜”优质题单推荐 10道题(C++ | 洛谷 | acwing)

这篇具有很好参考价值的文章主要介绍了【DFS专题】深度优先搜索 “暴搜”优质题单推荐 10道题(C++ | 洛谷 | acwing)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【DFS专题】优质题单推荐 10道题(C++ | 洛谷 | acwing)

题单

  • 来自b站大佬的题单
  • 题单链接
    【DFS专题】深度优先搜索 “暴搜”优质题单推荐 10道题(C++ | 洛谷 | acwing)

一、模板 [极为重要]

全排列DFS

【DFS专题】深度优先搜索 “暴搜”优质题单推荐 10道题(C++ | 洛谷 | acwing)

  • 每个位置选什么数
#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

【DFS专题】深度优先搜索 “暴搜”优质题单推荐 10道题(C++ | 洛谷 | acwing)

  • 与全排列的差别就是第二个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

【DFS专题】深度优先搜索 “暴搜”优质题单推荐 10道题(C++ | 洛谷 | acwing)

  • 参数 : 前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 种方案数
    【DFS专题】深度优先搜索 “暴搜”优质题单推荐 10道题(C++ | 洛谷 | acwing)
    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

image-20230324100814102

  • 为什么要 m + 1

image-20230324183719886

#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

image-20230324105810729

image-20230324110048013

  • 思路一 、 模拟
    image-20230324110828519
  • 思路二 :预处理 + 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

image-20230324160352460

#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 奇怪的电梯 暴力

image-20230324170248812

Ki 的值 表示 上 or 下 的层数

  • 学个思路就可以
    image-20230324171907454

image-20230324171926764

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求图的连通块】

image-20230324172618971

#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;
}

在这里插入图片描述文章来源地址https://www.toymoban.com/news/detail-402103.html

到了这里,关于【DFS专题】深度优先搜索 “暴搜”优质题单推荐 10道题(C++ | 洛谷 | acwing)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 深度优先搜索(DFS)和广度优先搜索(BFS)

    代码随想录 深度优先搜索和广度优先搜索,都是图形搜索算法,它两相似,又却不同,在应用上也被用到不同的地方。这里拿一起讨论,方便比较。 先给大家说一下两者大概的区别: 如果搜索是以接近起始状态的程序依次扩展状态的,叫广度优先搜索。 如果扩展是首先扩展

    2024年02月02日
    浏览(55)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)

    深度优先搜索(DFS)和广度优先搜索(BFS)是图论中两个非常重要的算法,主要用于拓扑排序,寻路(走迷宫)和搜索引擎等。在我们写算法时经常会遇到需要使用DFS和BFS的题目,例如leetcode中的岛屿相关的问题以及有关树的题目大多都会使用DFS或者BFS。 深度优先搜索 深度优

    2024年02月10日
    浏览(47)
  • 【数据结构与算法】图遍历算法 ( 深度优先搜索 DFS | 深度优先搜索和广度优先搜索 | 深度优先搜索基本思想 | 深度优先搜索算法步骤 | 深度优先搜索理论示例 )

    图 的 遍历 就是 对 图 中的 结点 进行遍历 , 遍历 结点 有如下两种策略 : 深度优先搜索 DFS 广度优先搜索 BFS \\\" 深度优先搜索 \\\" 英文名称是 Depth First Search , 简称 DFS ; DFS 基本思想 : 访问第一个邻接结点 : 从 起始点 出发 , 该 起始点 可能有 若干 邻接结点 , 访问 第一个 邻接结点

    2024年02月02日
    浏览(48)
  • 深度优先搜索(DFS)算法

    目录 算法思想 时间复杂度和空间复杂度 算法实现 算法优缺点 应用领域 深度优先搜索(DFS)算法的思想是从图的某个起始顶点开始,沿着一条路径尽可能深入地访问图中的所有顶点,直到不能继续为止,然后返回并探索其他路径。具体而言,DFS算法使用栈数据结构来实现,

    2024年02月05日
    浏览(46)
  • DFS—深度优先搜索

    递归函数代码形式 1 1 2 3 5 8 13 21 34 55 89 ... 已知前两项为1,之后每一项等于前两项之和。 现输入n,请输出兔子数列的第n项。 F ( n ) = { 1 ( n = 0 ) n ∗ F ( n − 1 ) ( n 0 ) F(n)=begin{cases}1(n=0)\\\\n*F(n-1)(n0)end{cases} F ( n ) = { 1 ( n = 0 ) n ∗ F ( n − 1 ) ( n 0 ) ​ 不难分析出

    2024年02月20日
    浏览(63)
  • DFS深度优先搜索

    DFS(Depth-First Search) 深度优先搜索,是一种常用的图遍历算法,用于在图或树数据结构中遍历所有节点。 深度优先搜索从一个起始节点开始,沿着一条路径尽可能远地访问节点,直到到达不能继续前进的节点,然后返回上一层继续探索其他路径。这个过程是递归的,通过不

    2024年02月04日
    浏览(36)
  • 深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)

    目录 深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜) 深度优先搜索(简称“深搜”或DFS) 广度优先搜索 总结 深度优先生成树和广度优先生成树 非连通图的生成森林 深度优先生成森林 广度优先生成森林 图 1 无向图 深度优先搜索的过程类似于树 的先序遍历 ,首先

    2024年01月20日
    浏览(49)
  • c++深度优先搜索DFS

    目录 介绍 实现过程 模板 例题详解 1.枚举排列 2.迷宫寻路 3.八皇后 剪枝与优化 作业 今天我们来学习一个极其重要的算法:深度优先搜索。 深度优先搜索,又叫DFS,是遍历图或者数的一种算法,本质就是递归。具体方法:先以一个节点为起点,向一个方向扩展,再以新的节

    2024年01月16日
    浏览(43)
  • 深度优先搜索(DFS)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法,总是以“深度”作为前进的。实现方式是有很多,最

    2024年02月08日
    浏览(52)
  • 深度优先搜索(DFS)和广度优先搜索(BFS),用代码讲原理

    以图文的形式对深度搜索和广度搜索的理论进行讲解时,可能会对一些概念有些模糊,且不太清楚怎么把该理论用程序的方式进行复现并解决这一搜索问题(这说的就是本人) 。所以后面我看完了一份实现这两种搜索方法的代码,在这做一个笔记,希望对大家有所帮助。 两

    2024年04月12日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包