dfs和bfs能解决的问题

news/2024/11/8 13:45:56/

一.理解暴力穷举之dfs和bfs

暴力穷举

暴力穷举是在解决问题中最常用的手段,而dfs和bfs算法则是这个手段的两个非常重要的工具。
其实,最简单的穷举法是直接遍历,如数列求和,遍历一个数组即可求得所问答案,这与我在前两篇博客中讲述的动态规划算法执行方式其实是一样的,其特点我们说过,有三个“可分解,可一次解决,可储存”,可分解是不管有多大多复杂的数据都能用同一种办法解决的前提,可一次解决,代表每一个子问题的解决答案即是当前最优解,也是全局最优解的子解,这叫做无后效性,无后效性其实表面意思是局部决策对全局决策无关,但准确来说,是局部决策的最优解之外的决策永远不会成为全局决策的子决策,最后若可储存子问题的答案,我们就可以实现直接遍历或动态规划得到我们所需要的答案。

dfs和bfs的特点

在前言我们提到了直接遍历的穷举办法,而动态规划也是其中之一,具有”可分解,可一次解决,可存储“的特点,而dfs和bfs与它们的唯一区别就是”不可一次解决“,也就是并非有最优解,子问题的每一个决策都有可能是全局解的子解,这叫做有后效性,但准确来说,是局部决策都可能会成为全局决策的子决策,那么如何解决这类问题呢,dfs和bfs算法就是这类问题的天敌

二.掌握dfs和bfs解决问题的方法

1.dfs通过其能够“回溯”的本领解决有后效性

例题

题目链接

分析

题目问的是,在给定n*n棋盘内,棋子位置相互不冲突的情况下,摆放在棋盘区域的棋子个数为k的方案数是多少
1.可先放前面的棋子,再放后面的棋子(可分解)
2.对每个棋盘位置都有放或不放两种决策,每个棋子的这两种决策都可能满足题意(有后效性)
3.在从前到后决策的过程中,可记录已放棋子个数(可存储)

代码

#include<iostream>
#include<cstdio>using namespace std;const int N = 100;
bool col[N],row[N];
char g[N][N];
int cnt = 0,n,m;
void dfs(int x,int y,int k)
{if(x == n) return;if(k == m) {cnt++;return;}if(y == n){y = 0;x++;}dfs(x,y+1,k);//先递归遍历左子树,即不放皇后的操作if(!col[y]&&!row[x]&&(g[x][y] == '#')){col[y] = row[x] = true;dfs(x,y+1,k+1);//再递归遍历右子树col[y] = row[x] = false;}
}
int main()
{while(1){scanf("%d%d",&n,&m);if(n == -1&&m == -1) break;for(int i = 0;i<n;i++)for(int j = 0;j<n;j++)cin>>g[i][j];dfs(0,0,0);printf("%d\n",cnt);cnt = 0;}return 0;
}

2.bfs通过其能够“排队”的本领解决有后效性

例题

题目链接

分析

题目问的是,在给定L*R*C迷宫内,从“S”走到“E”至少需要多少分钟
1.可一步一步走(可分解)
2.对每一步都有上下左右前后,每一步的决策都可能满足题意(有后效性)
3.在从前到后决策的过程中,可记录已用掉多少分钟(可存储)

代码

#define _CRT_SECURE_NO_WARNINGS
//#define LOCAL
#include <iostream>
#include <cstring>
#include <queue>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=35;
int L,R,C;
int sx,sy,sz,ex,ey,ez;
bool flag;
char g[N][N][N];
bool st[N][N][N];
int dist[N][N][N];
struct Node
{int z,x,y;
};
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
void bfs(int sz,int sx,int sy)
{memset(dist,0x3f,sizeof dist);Node input;input.z=sz,input.x=sx,input.y=sy;queue<Node>q;q.push(input);st[sz][sx][sy]=1;dist[sz][sx][sy]=0;while(q.size()){Node t=q.front();if(t.z==ez&&t.x==ex&&t.y==ey){flag=1;break;}q.pop();for(int i=0;i<6;i++){int a=t.z+dz[i];int b=t.x+dx[i];int c=t.y+dy[i];if(a<0||b<0||c<0||a>=L||b>=R||c>=C)continue;if(st[a][b][c]||g[a][b][c]=='#')continue;st[a][b][c]=1;Node tmp;tmp.z=a,tmp.x=b,tmp.y=c;q.push(tmp);dist[a][b][c]=dist[t.z][t.x][t.y]+1;}}
}
void solve()
{while(~scanf("%d%d%d",&L,&R,&C)&&(L||R||C)){for(int i=0;i<L;i++)for(int j=0;j<R;j++)scanf("%s",g[i][j]);for(int i=0;i<L;i++)for(int j=0;j<R;j++)for(int k=0;k<C;k++){if(g[i][j][k]=='S')sz=i,sx=j,sy=k;if(g[i][j][k]=='E')ez=i,ex=j,ey=k;}memset(st,0,sizeof st);flag=0;bfs(sz,sx,sy);if(flag) printf("Escaped in %d minute(s).\n",dist[ez][ex][ey]);else puts("Trapped!");}return;
}int main()
{
#ifdef LOCALfreopen("data.in", "r", stdin);freopen("data.out", "w", stdout);
#endifint t = 1;//cin>>t;while(t--){solve();}return 0;
}

~感谢观看❥(^_-)


http://www.ppmy.cn/news/34630.html

相关文章

蓝桥杯刷题第二十天

第一题&#xff1a;纸张尺寸问题描述在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm 841mm, 将 A0 纸 沿长边对折后为 A1 纸, 大小为 841mm 594mm, 在对折的过程中长度直接取 下整 (实际裁剪时可能有损耗)。将 A1 纸沿长边对折后为 A2 纸, 依此类推。输入纸张的名称, 请输出…

如何在 Vue 中使用 防抖 和 节流

大厂面试题分享 面试题库前后端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★地址&#xff1a;前端面试题库 https://mp.weixin.qq.com/s?__bizMzU5NzA0NzQyNg&mid2247485824&idx3&sn70cd26a7c0c683de64802f6cb9835003&scene21#wech…

WPF毛笔字实现过程

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…

【面试】-- Hive高频面试题目

一、请描述一下数据倾斜,并提供解决方案?  定义:由于数据分布不均匀,导致大量数据集中到一点,造成数据热点。现象是100个 task, 有一个运行了 1个小时,其他99个只有 10分钟。本质是数据量太大。原因:key 分布不均匀、sql倾斜join、建表时类型有问题算子:count、dist…

蓝桥杯每日一真题—— [蓝桥杯 2021 省 AB2] 完全平方数(数论,质因数分解)

文章目录[蓝桥杯 2021 省 AB2] 完全平方数题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1样例 #2样例输入 #2样例输出 #2提示思路&#xff1a;理论补充&#xff1a;完全平方数的一个性质&#xff1a;完全平方数的质因子的指数一定为偶数最终思路&#xff1a;小插曲&am…

Nginx可视化管理工具 - Nginx Proxy Manager

一、介绍 nginx-proxy-manager 是一个反向代理管理系统,它基于Nginx,具有漂亮干净的 Web UI。还可以获得受信任的 SSL 证书,并通过单独的配置、自定义和入侵保护来管理多个代理。 其官网地址如下: https://nginxproxymanager.com/ 二、安装 第一步:192.168.1.108服务…

五.ElasticSearch的基础+实战

五.ElasticSearch的基础+实战 1.Elasticsearch的是什么? 2.Elasticsearch的作用是什么? 3.Elasticsearch的核心思想? 4.Elasticsearch启动与简单使用 5.kibana结合elasticsearch实现简单的增删改查 6.elasticsearch安装中文分词器 7.elasticsearch结合springboot开发…

STM32 ADC+定时器+DMA+FFT

本次实现的功能为单片机DAC输出一个正弦波&#xff0c;然后ADC定时采样用DMA输出&#xff0c;最后对DAC输出的波形进行FFT。单片机STM32F103ZET6内部时钟一、配置ADCADC端口为PA1&#xff0c;采用DMA输出&#xff0c;定时器3触发定时器时钟64M&#xff0c;分频后为102.4KHzADC采…