DFS的一些题目

题目1:奶牛选美

这道题其实就是把两个连通块合成一个,可以用dfs、bfs和并查集。因为最近在dfs专题训练,这里我只写了dfs。

首先我们用dfs的方式遍历两个连通块,将两个连通块中点的坐标分别存入两个数组中,将这两个数组中的点一 一匹配,迭代出最小值。

#include<iostream>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
vector<PII> points[2];
const int N=55;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int n,m;
char g[N][N];
void dfs(int x,int y,vector<PII> &q)
{
    q.push_back({x,y});
    g[x][y]='.';
    for(int i=0;i<4;i++)
    {
        int cx=x+dx[i],cy=y+dy[i];
        if(cx<0||cx>=n||cy<0||cy>=m) continue;
        if(g[cx][cy]=='X') dfs(cx,cy,q);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%s",g[i]);
    int k=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(g[i][j]=='X') dfs(i,j,points[k++]);
        }
    int res=N*N;
    
    for(int i=0;i<points[0].size();i++)
        for(int j=0;j<points[1].size();j++)
        {
            int x1=points[0][i].x,y1=points[0][i].y;
            int x2=points[1][j].x,y2=points[1][j].y;
            int t=abs(x1-x2)+abs(y1-y2)-1;
            res=min(res,t);
        }
    printf("%d",res);
}

题目2:大臣的旅费

首先是最暴力的写法。

以每个点为起点,搜索它的最长路径,最后取所有点为起点时最长路径的最大值。

时间复杂度是O(n^{2})。

#include<iostream>
#include<cstring>
using namespace std;
const int N=2e5+10;
int h[N],e[N],ne[N],w[N],idx=0;
int n;
bool st[N];
int sum=0;
void add(int p,int q,int d)
{
    e[idx]=q;
    w[idx]=d;
    ne[idx]=h[p];
    h[p]=idx++;
}
int dfs(int u,int res)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(st[j]) continue;
        st[j]=1;
        sum=max(sum,dfs(j,res+w[i]));
        st[j]=0;
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    memset(h,-1,sizeof(h));
    for(int i=1;i<n;i++) 
    {
        int p,q,d;
        scanf("%d%d%d",&p,&q,&d);
        add(p,q,d);
        add(q,p,d);
    }
    int res=0;
    
    for(int i=1;i<=n;i++) 
    {
        memset(st,0,sizeof(st));
        st[i]=1;
        dfs(i,0);
    }
    printf("%d",((10+1)+(10+sum))*sum/2);
}

接下来考虑该如何优化。

这其实涉及到一个知识点——求树的直径。这个问题有固定的步骤:

①选定一个x,求出x到所有点的距离;

②找到与x距离最远的点y,求出y到所有点的距离;

③y到所有点的最长距离即为答案。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int h[N],e[N],ne[N],w[N],idx=0;
int n;
bool st[N];
int dist[N];
void add(int p,int q,int d)
{
    e[idx]=q;
    w[idx]=d;
    ne[idx]=h[p];
    h[p]=idx++;
}
void dfs(int u,int di)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(dist[j]!=-1) continue;
        dist[j]=di+w[i];
        dfs(j,dist[j]);
    }
}
int main()
{
    scanf("%d",&n);
    memset(h,-1,sizeof(h));
    for(int i=1;i<n;i++) 
    {
        int p,q,d;
        scanf("%d%d%d",&p,&q,&d);
        add(p,q,d);
        add(q,p,d);
    }
    memset(dist,-1,sizeof(dist));
    dist[1]=0;
    dfs(1,0);
    int maxpoint=0,maxval=0;
    for(int i=1;i<=n;i++)
        if(dist[i]>maxval)
        {
            maxval=dist[i];
            maxpoint=i;
        }
    memset(dist,-1,sizeof(dist));
    dist[maxpoint]=0;
    dfs(maxpoint,0);
    sort(dist+1,dist+1+n);
    int res=dist[n];
    printf("%lld",(long long)(10+1+10+res)*res/2);
    
}

题目3:扫雷

这道题的过程是:遍历排雷火箭,如果排雷火箭的范围(遍历-r到r之间在圆内的所有点)波及到了炸弹,则炸弹爆炸,dfs炸弹的范围。

这道题过完所有数据需要手写哈希,这里没有手写,过了8/11个数据。

#include<iostream>
#include<unordered_map>
using namespace std;
const int N=5e4+10,M=1e9+1;
typedef pair<int,int> PII;
typedef long long ll;
#define x first
#define y second
int n,m;
pair<PII,int> jian[N],lei[N];
unordered_map<ll,int> is_lei;
unordered_map<ll,int> num;
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
int cnt=0;
void dfs(int x,int y,int r)
{
    for(int cx=max(0,x-r);cx<=x+r;cx++)
        for(int cy=max(0,y-r);cy<=y+r;cy++)
        {
            if((cx-x)*(cx-x)+(cy-y)*(cy-y)>r*r) continue; 
            ll t;
            t=cx*M+cy;
            
            if(is_lei.count(t)) 
            {
                cnt+=num[t];
                int tr=is_lei[t];
                is_lei.erase(t);
                num.erase(t);
                dfs(cx,cy,tr);
            }
        }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&lei[i].x.x,&lei[i].x.y,&lei[i].y);
    for(int i=1;i<=n;i++) 
    {
        ll t;
        t=lei[i].x.x*M+lei[i].x.y;
        
        if(is_lei.count(t)) 
        {
            is_lei[t]=max(is_lei[t],lei[i].y);
            num[t]++;
        }
        else 
        {
            is_lei[t]=lei[i].y;
            num[t]=1;
        }
    }
    for(int i=1;i<=m;i++) scanf("%d%d%d",&jian[i].x.x,&jian[i].x.y,&jian[i].y);
    for(int i=1;i<=m;i++) dfs(jian[i].x.x,jian[i].x.y,jian[i].y);
    printf("%d",cnt);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/461882.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

AI预测福彩3D第10弹【2024年3月16日预测--第2套算法重新开始计算第2次测试】

今天继续开始咱们第2套算法的验证&#xff0c;计划每套算法连续测试10期&#xff0c;达到50%的命中率即为较优的模型&#xff0c;可继续使用。老规矩&#xff0c;先上图表&#xff0c;再下结论~ 最终&#xff0c;经过研判分析&#xff0c;2024年3月16日福彩3D的七码预测结果如下…

LeetCode 面试经典150题 26.删除有序数组中的重复项

题目&#xff1a; 给你一个 非严格递增排列 的数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次 &#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量…

重学SpringBoot3-整合SSM

更多SpringBoot3内容请关注我的专栏&#xff1a;《SpringBoot3》 期待您的点赞&#x1f44d;收藏⭐评论✍ 重学SpringBoot3-整合SSM Spring Boot整合SSM示例1. 创建Spring Boot项目2. 配置数据源3. 配置MyBatis4. 实现数据访问对象&#xff08;DAO&#xff09;5. 编写服务层和控…

强化学习------DDPG算法(附pytorch代码)

目录 一、前言二、基本原理2.1、经验回放2.2、更新过程2.2.1、Critic网络更新过程2.2.2、Actor网络更新过程2.2.3、 目标网络的更新 2.3、噪音探索 三、算法代码实现四、训练示例4.1、实现效果 一、前言 Deep Deterministic Policy Gradient (DDPG)算法是DeepMind团队提出的一…

YOLOv5_seg-Openvino和ONNXRuntime推理【CPU】

纯检测系列&#xff1a; YOLOv5-Openvino和ONNXRuntime推理【CPU】 YOLOv6-Openvino和ONNXRuntime推理【CPU】 YOLOv8-Openvino和ONNXRuntime推理【CPU】 YOLOv7-Openvino和ONNXRuntime推理【CPU】 YOLOv9-Openvino和ONNXRuntime推理【CPU】 跟踪系列&#xff1a; YOLOv5/6/7-O…

一文总结python的异常数据处理示例

AI应用开发相关目录 本专栏包括AI应用开发相关内容分享&#xff0c;包括不限于AI算法部署实施细节、AI应用后端分析服务相关概念及开发技巧、AI应用后端应用服务相关概念及开发技巧、AI应用前端实现路径及开发技巧 适用于具备一定算法及Python使用基础的人群 AI应用开发流程概…

【打工日常】使用Docker部署团队协作文档工具

一、ShowDoc介绍 ​ShowDoc是一个适合IT团队共同协作API文档、技术文档的工具。通过showdoc&#xff0c;可以方便地使用markdown语法来书写出API文档、数据字典文档、技术文档、在线excel文档等等。 响应式网页设计&#xff1a;可将项目文档分享到电脑或移动设备查看。同时也可…

redis持久化策略

redis中持久化策略 1.持久化是什么 在前面的过程中讲述了有关于MySQL中事务的一些特性以及隔离等级。其中很重要的一条就提到了持久化&#xff0c;持久化就是可以将数据进行一个持久保存的意思。也就是将数据写入到硬盘中&#xff0c;虽然&#xff0c;redis是操作内存的一个数…

element-plus怎么修改表单中的label字体颜色及大小

问题描述&#xff1a; 当我们在vue3中使用element-plus组件库提供的表单组件时&#xff0c;有时我们需要修改表单中label的字体颜色等属性&#xff0c;这是如果直接选中label的class进行修改是不起作用的&#xff0c;我们只需深度选择即可选中并进行修改。 比如&#xff1a; …

PS学习-抠图-蒙版-冰块酒杯等透明物体

选中图&#xff0c;ctrlA 全选 ctrlC复制 创建一个蒙版图层 选中蒙版Alt 点击进入 ctrlv 复制 ctrli 反转 原图层 ctrldelete填充为白色 添加一个背景&#xff0c;这个方法通用 首选创建一个 拖到最底部 给它填充颜色 这个可能是我图片的原因。视频是这样做的

力扣L10--- 3. 无重复字符的最长子串--2024年3月14日

1.题目 2.知识点 注1&#xff1a;containsKey 是 Java 中 HashMap 类的一个方法&#xff0c;用于检查哈希表中是否包含指定的键。 注2&#xff1a;在哈希表&#xff08;HashMap)中&#xff0c;每个键对应着唯一的值&#xff0c;因此键不能重复&#xff0c;但值可以重复。 (1)创…

公众号留言功能恢复了,你的开通了吗?

了解公众号的人都知道&#xff0c;腾讯在2018年3月宣布暂停新注册公众号的留言功能&#xff0c;这之后注册的公众号都不具备留言功能。 这成了很多号主运营人的一块心病&#xff0c;也包括我。 没有留言&#xff0c;就好似一个人玩单机游戏&#xff0c;无法与读者互动&#xff…

数据资产管理解决方案:构建高效、安全的数据生态体系

在数字化时代&#xff0c;数据已成为企业最重要的资产之一。然而&#xff0c;如何有效管理和利用这些数据资产&#xff0c;却是许多企业面临的难题。本文将详细介绍数据资产管理解决方案&#xff0c;帮助企业构建高效、安全的数据生态体系。 一、引言 在信息化浪潮的推动下&a…

DVWA-File Upload文件上传

什么是文件上传漏洞&#xff1f; 黑客利用文件上传后服务器解析处理文件的漏洞上传一个可执行的脚本文件&#xff0c;并通过此脚本文件获得了执行服务器端命令的能力。 造成文件上传漏洞的原因: 1.服务器配置不当 2.开源编辑器上传漏洞 3.本地文件上传限制被绕过 4.过滤不严格被…

【C语言】分支语句(逻辑运算符与关系运算符)

文章目录 **逻辑运算符(&&、||、!)**逻辑运算符特点短路短路-逻辑与短路-逻辑或 **关系运算符&#xff08;relational expression&#xff09;**运算操作符的结合律、运算符 **选择结构/分支结构****if 语句****复合句的if语句(if...else..语句)****不良风格的程序** *…

使用Loadrunner进行性能测试

一、确定性能测试的范围、要求、配置、工具等 明确测试的系统&#xff1a; 本文档主要指的是web应用。 明确测试要求&#xff1a; 用户提出性能测试&#xff0c;例如&#xff0c;网站首页页面响应时间在3S之内&#xff0c;主要的业务操作时间小于10s&#xff0c;支持300用户在…

【触想智能】嵌入式工控一体机在交通监控管理上的应用分析

随着现代交通网络和技术的不断发展&#xff0c;高速公路的建设已经成为国家重点工程之一。然而&#xff0c;如何确保高速公路的安全驾驶则成为了一个长期亟待解决的问题。 为了提高高速公路的交通管理效率&#xff0c;嵌入式工控一体机被广泛应用于高速公路的联合监控管理系统中…

《古滇传说水龙吟》敖诀扮演者李亚云

2024年2月28日&#xff0c;演员李亚云参演新剧古滇传说原创系列剧第一部《水龙吟》在浙江横店影视城开机拍摄。该剧由中共昆明市西山区委宣传部、石林县委宣传部、昆明滇池国家旅游度假区管委会文旅投促局、云南民族电影制片厂、云南卫视、昆明影视拍摄服务中心支持&#xff0c…

[RAM] RAM 突发传输(Burst ,Burst size, length) | Burst 读写过程与时序 精讲

主页&#xff1a; 元存储博客 文章目录 前言1. Burst 基本概念含义Burst Width &Burst Length 2. CPU Burst mode3. 总线 burst mode总线的仲裁总线突发传输时序 4. Burst Chop (突发终止)5. Burst Mode 应用什么时候用突发模式 总结 前言 在DMA&#xff08;直接内存访问&…

java基础-异常、常用类

异常 Exception 如果程序员认为一段代码可能出现异常/问题&#xff0c;try-catch异常处理机制来解决&#xff0c;从而保证程序的健壮性。将该代码块–》选中–》快捷键 ctrlaltt–》选中 try-catch 常见的一些异常~ 异常体系图&#xff0c;体现了继承和实现关系。&#xff08…