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

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...