当前位置: 首页 > 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 文件精简且准确&…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

Yolo11改进策略:Block改进|FCM,特征互补映射模块|AAAI 2025|即插即用

1 论文信息 FBRT-YOLO&#xff08;Faster and Better for Real-Time Aerial Image Detection&#xff09;是由北京理工大学团队提出的专用于航拍图像实时目标检测的创新框架&#xff0c;发表于AAAI 2025。论文针对航拍场景中小目标检测的核心难题展开研究&#xff0c;重点解决…...