当前位置: 首页 > news >正文

蓝桥杯倒计时47天!DFS基础——图的遍历

倒计时47天!

深度优先搜索——DFS

温馨提示:学习dfs之前最好先了解一下递归的思想。

DFS基础——图的遍历

仙境诅咒

问题描述

在一片神秘的仙境中,有N位修仙者,他们各自在仙境中独立修炼,拥有自己独特的修炼之道和修炼之地,修仙者们彼此之间相互尊重、和谐相处。

然而,有一天,仙境的主宰者妮妮(第一位修仙者)受到了诅咒,该诅咒会向距离妮妮不超过D的范围内的修仙者传播。也就是说,如果一个修仙者被诅咒,那么在距离他不超过D的范围内的所有修仙者都会被诅咒。

现在,你需要预测哪些修仙者最终会被诅咒,以便及时采取措施,保护仙境的和平与安宁。

输入格式

第一行输入一个正整数 N ( 1 < N ≤ 1 0 3 ) N(1<N≤10^3) N(1<N103),表示仙境中有N位修仙者。

接下来N行,每行两个实数 X i X_i Xi Y i Y_i Yi$ (-103≤X_i,Y_i≤103) ,表示第 i 位修仙者的坐标 ,表示第i位修仙者的坐标 ,表示第i位修仙者的坐标(X_i,Y_i)$。第一位修仙者即仙境的主宰者妮妮。

最后一行输入一个正整数 D ( 1 < = D < = 1 0 3 ) D (1<=D<= 10^3) D(1<=D<=103),表示诅咒传播的范围。

输出格式

输出N行,每行一个整数,第i行的整数为1表示第i位修仙者最终被诅咒,为0则表示第i位修仙者没有被诅咒。

样例输入

5
0 0
1 1
0 1
1 0
2 2
1

样例输出

1
1
1
1
0
题目分析

距离被诅咒者距离不超过D是其它修仙者都会被诅咒感染,也就是我可以从当前被诅咒者走到距离不超过D的其它修仙者。我们可以用数组v[i]=1表示修仙者i已经被诅咒。那么dfs过程代码如下,

private static void dfs(int u) {v[u] = 1;for(int i = 1;i <=n;i++)if(v[i]==0&&dis(u,i)<=d)dfs(i);
}

dfs(u)这里的u是已经被诅咒的修仙者,那么v[u]就要被标记为1,然后for循环遍历其它修仙者,如果其它修仙者没有被诅咒,并且与当前节点u的距离小于d,那么说明当前修仙者会被传染成为新的被诅咒者,这个时候就要进入dfs(i)去看i能传染给哪些人。

为什么要判断v[i]==0?防止重复遍历,比如我从节点2进入了节点3,即dfs(2)进入了dfs(3),在dfs(3)运行时,我判断了dis(2,3)<=d,如果我没有v[i]==0的约束,我会从dfs(3)进入dfs(2),再从dfs(2)进入dfs(3),最终产生了死循环。

dis函数就是已知两点坐标求两点距离的公式,很简单,但是注意,这里有开根号,那么会有小数,在定义变量的时候要注意变量的类型。

private static double dis(int u, int v) {return Math.sqrt(Math.pow(x[u]-x[v], 2)+Math.pow(y[u]-y[v], 2));
}

最后通过数组v的值是否为1,可以判断当前点是否被传染。

for(int i = 1;i <=n;i++) System.out.println(v[i]==0?0:1);
题目代码
import java.util.Scanner;
public class Main{static int n,d;static double x[],y[];static int v[];
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();x = new double[n+1];y = new double[n+1];v = new int[n+1];for(int i = 1;i <= n;i++) {x[i] = scanner.nextInt();y[i] = scanner.nextInt();}d = scanner.nextInt();dfs(1);for(int i = 1;i <=n;i++) System.out.println(v[i]==0?0:1);
}
private static void dfs(int u) {// TODO Auto-generated method stubv[u] = 1;for(int i = 1;i <=n;i++)if(v[i]==0&&dis(u,i)<=d)dfs(i);
}
private static double dis(int u, int v) {// TODO Auto-generated method stubreturn Math.sqrt(Math.pow(x[u]-x[v], 2)+Math.pow(y[u]-y[v], 2));
}
}

相关文章:

蓝桥杯倒计时47天!DFS基础——图的遍历

倒计时47天&#xff01; 深度优先搜索——DFS 温馨提示&#xff1a;学习dfs之前最好先了解一下递归的思想。 DFS基础——图的遍历 仙境诅咒 问题描述 在一片神秘的仙境中&#xff0c;有N位修仙者&#xff0c;他们各自在仙境中独立修炼&#xff0c;拥有自己独特的修炼之道…...

体验LobeChat搭建私人聊天应用

LobeChat是什么 LobeChat 是开源的高性能聊天机器人框架&#xff0c;支持语音合成、多模态、可扩展的&#xff08;Function Call&#xff09;插件系统。支持一键免费部署私人 ChatGPT/LLM 网页应用程序。 地址&#xff1a;https://github.com/lobehub/lobe-chat 为什么要用Lobe…...

ClickHouse 指南(三)最佳实践 -- 主键稀疏索引

在ClickHouse主索引的实用介绍 ClickHouse release 24.1, 2024-01-30 1、简介 在本指南中&#xff0c;我们将深入研究ClickHouse索引。我们将详细说明和讨论: ClickHouse中的索引与传统的关系数据库管理系统有何不同ClickHouse是如何构建和使用表的稀疏主索引的什么是在Clic…...

【Nginx】Nginx配置反向代理 和 https

nginx.conf配置 进入linux /etc/nginx/ 打开nginx.conf 进行以下配置 http {include mime.types;default_type application/octet-stream;sendfile on;keepalive_timeout 65;server {#监听443端口listen 443 ssl;#你的域名server_name huiblog.top;#ssl证书的pe…...

ChatGPT第七讲

ChatGPT为什么会被热炒&#xff1f; 2023年上半年&#xff0c;ChatGPT引起了广泛的热议&#xff0c;对于ChatGPT有多热&#xff0c;不需要我重复了&#xff0c;你可能在网上看到了很多报道&#xff0c;标题如《ChatGPT揭开AI战幔&#xff1a;杀死黄页一样摧毁Google&#xff1f…...

Chapter 2 of Effective C++ (构造/析构/赋值运算)

条款06&#xff1a;了解C默默编写并调用哪些函数 Know what functions C silently writes and calls 编译器会为空类生成一个copy构造函数、copy assignment操作符和一个析构函数。此外如果你没有声明任何构造函数&#xff0c;它也会生成一个默认构造函数。 &#xff08;对C1…...

Android学习笔记 service启动方式

在Android系统中&#xff0c;Service的启动方式主要有两种&#xff1a; ## 1. startService 这种方式用于启动一个服务执行后台任务&#xff0c;不进行通信。当你调用startService()方法启动服务后&#xff0c;服务会一直无限期运行下去&#xff0c;只有在外部调用了stopServi…...

Redis 工具类 与 Redis 布隆过滤器

Redis 工具类 1. 核心依赖 <!--redis--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId> </dependency> <dependency><groupId>com.google.guava…...

自定义el-upload 上传文件

前言 最近在做一个文件上传的功能&#xff0c;后端接口写好了、发现前端上传文件的页面不会写……&#xff08;我很笨的&#xff09;然后我就找啊找发现element有个组件是<el-upload/>能直接上传文件。我就想直接用拿来改改改成自己想要的&#xff0c;可是就是这样我花了…...

LeetCode69. x 的平方根(C++)

LeetCode69. x 的平方根 题目链接代码 题目链接 https://leetcode.cn/problems/sqrtx/description/ 代码 class Solution { public:int mySqrt(int x) {int right x, left 0, ans -1;while(left < right){long long mid left (right - left) / 2;if(mid * mid <…...

[c++] 单例模式 + cyberrt TimingWheel 单例分析

单例模式要求一个类在一个进程中只能创建一个对象。比如 cyberrt 中的 TimingWheel 类就是单例模式&#xff0c;这个类管理着一个进程内的所有定时器&#xff0c;只需要一个对象就可以。 单例模式的实现有两种方式&#xff0c;懒汉式和饿汉式。懒汉式&#xff0c;当第一次使用…...

如何在cmd里面创建一个vue项目

在命令提示符&#xff08;CMD&#xff09;中创建一个Vue项目&#xff0c;你需要先确保你已经全局安装了Vue CLI&#xff08;Vue的命令行工具&#xff09;。如果你还没有安装Vue CLI&#xff0c;可以通过以下命令进行安装&#xff1a; bash复制代码 npm install -g vue/cli # O…...

Day2 JS基础

2.1 运算符 赋值运算符 一元运算符 -- <script>let h20let kh hconsole.log(h) //22console.log(k) //42let i1console.log(i i i) //7 ​// 递增运算符&#xff1a;var a8aconsole.log(a) //9 ​var num10var bnumconsole.log(b) //10</script> 比较运…...

mybatis----有用配置知识归纳(狂神说学习总结)

1.mybatis介绍 MyBatis 是一款优秀的持久层框架MyBatis 避免了几乎所有的 JDBC 代码和手动设置参数以及获取结果集的过程MyBatis 可以使用简单的 XML 或注解来配置和映射原生信息&#xff0c;将接口和 Java 的 实体类映射成数据库中的记录 官网 Mybatis中文官方文档 : https…...

【TCP/IP】组播

一、组播介绍 组播&#xff08;Multicast&#xff09;是网络技术中数据传输的一种方法&#xff0c;它允许将数据包同时发送给一组指定的目标&#xff0c;而不是单个的目标&#xff08;单播 Unicast&#xff09;或所有可能的目标&#xff08;广播 Broadcast&#xff09;。组播传…...

java 内存模型

程序计数器 线程私有主要字节码解释器通过读取程序计数器来选取下一条需要执行的指令&#xff0c;比如分支&#xff0c;循环&#xff0c;跳转和异常处理如果执行的是java 方法&#xff0c;那么程序计数器记录的时候虚拟机字节码指令的地址&#xff0c;如果执行的是native 方法…...

Linux——缓冲区封装系统文件操作

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、FILE二、封装系统接口实现文件操作1、text.c2、mystdio.c3、mystdio.h 一、FILE 因为IO相…...

深度学习系列59:文字识别

1. 简单文本&#xff1a; 使用google加的tesseract&#xff0c;效果不错。 首先安装tesseract&#xff0c;在mac直接brew install即可。 python调用代码&#xff1a; import pytesseract from PIL import Image img Image.open(1.png) pytesseract.image_to_string(img, lan…...

学习JAVA的第七天(基础)

目录 static 静态变量 静态方法 工具类&#xff1a; static的注意事项 继承 继承的好处 继承的特点 方法的重写 书写格式 override重写注解 方法重写的要求 this关键字 super关键字 static static表示静态&#xff0c;是Java中的一个修饰符&#xff0c;可以修饰成…...

GoLand 相关

goland 下载依赖 go mod tidy&#xff1a;保持依赖整洁 go mod tidy 命令的作用是清理未使用的依赖&#xff0c;并更新 go.mod 以及 go.sum 文件。 go mod tidy 和 go mod vendor 两个命令是维护项目依赖不可或缺的工具。go mod tidy 确保了项目的 go.mod 文件精简且准确&…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...

大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程

基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...

Redis——Cluster配置

目录 分片 一、分片的本质与核心价值 二、分片实现方案对比 三、分片算法详解 1. ‌范围分片&#xff08;顺序分片&#xff09;‌ 2. ‌哈希分片‌ 3. ‌虚拟槽分片&#xff08;Redis Cluster 方案&#xff09;‌ 四、Redis Cluster 分片实践要点 五、经典问题解析 C…...