【蓝桥杯每日一题】扫雷
扫雷
知识点
2024-12-3 蓝桥杯每日一题 扫雷 dfs （bfs也是可行的）
题目大意
在一个二维平面上放置这N个炸雷，每个炸雷的信息有$(x_i,y_i,r_i) $，前两个是坐标信息，第三个是爆炸半径。然后会输入M个排雷火箭，同样的信息；排雷火箭会将范围内所有的炸雷炸掉，并且会引发一连串爆炸这就要根据爆炸半径来判断。
解题思路
- 要考虑怎么存储这个炸弹信息，并且还要方便遍历到。在题目中坐标范围是 1 0 9 10^9 109,肯定不能存到二维数组的平面坐标中。
- 使用 m a p < p a i r < i n t , i n t > , v e c t o r < i n t > > map<pair<int,int>,vector<int>> map<pair<int,int>,vector<int>>，这样方便以O(1)的时间访问到当前位置，并且题目中明确表示同一个点可能会包含多个炸雷或火箭，（这一点一定看清楚），我就是这一点磕了一下；然后就是一定要使用map来定义，unordered_map我用的不行，应为这里使用到了pair。
- 最后就是递归遍历了，没输入一个火箭调用dfs；而且注意到 r 的的范围是很小的，我们就可以通过遍历当前位置为中心向四周扩展 r 长度的正方形，然后找到雷之后还要判断两点之间的距离是否在园内即可。
Accepted
#include <bits/stdc++.h>
using namespace std;const int N = 5e4+10;
typedef long long ll;
typedef pair<int,int> pii;
int n,m,cnt;
map<pii,vector<int>> a;
// 两点之间的距离
ll dist(int x1,int y1,int x2,int y2) {return 1ll*(x1-x2)*(x1-x2) + 1ll*(y1-y2)*(y1-y2);
}void dfs(int x,int y,int r) {for(int i = x-r;i <= x+r;i++) {for(int j = y-r;j <= y+r;j++) {if(a.count({i,j})) {int len = a[{i,j}].size();for(int k = 0;k < len;k++) {int rr = a[{i,j}][k];if(rr > 0 && dist(i,j,x,y) <= 1ll*r*r) {a[{i,j}][k] = 0;cnt++;dfs(i,j,rr);}}}}}
}int main()
{int x,y,r;cin>>n>>m;for(int i = 1;i <= n;i++) {cin>>x>>y>>r;a[{x,y}].push_back(r);}while(m--) {cin>>x>>y>>r;dfs(x,y,r);}cout<<cnt;return 0;
}
备注
欢迎大家一起来备战蓝桥杯。可以私信我加联系方式，人多的话咱就拉个群了。
相关文章：
【蓝桥杯每日一题】扫雷
扫雷 知识点 2024-12-3 蓝桥杯每日一题 扫雷 dfs （bfs也是可行的） 题目大意 在一个二维平面上放置这N个炸雷，每个炸雷的信息有$(x_i,y_i,r_i) $，前两个是坐标信息，第三个是爆炸半径。然后会输入M个排雷火箭࿰…...
以nlp为例，区分BatchNorm、LayerNorm、GroupNorm、RMSNorm
以nlp中一个小批次数据，详细区分BatchNorm、LayerNorm、GroupNorm、RMSNorm。这几种归一化的不同。如下表格，从计算范围、统计量、计算复杂度以及应用场景等方面的差异给出。 方法计算范围统计量计算复杂度应用场景BatchNorm跨所有句子的同一维度使用批…...
（软件测试文档大全）测试计划，测试报告，测试方案，压力测试报告，性能测试，等保测评，安全扫描测试，日常运维检查测试，功能测试等全下载
1. 引言 1.1. 编写目的 1.2. 项目背景 1.3. 读者对象 1.4. 参考资料 1.5. 术语与缩略语 2. 测试策略 2.1. 测试完成标准 2.2. 测试类型 2.2.1. 功能测试 2.2.2. 性能测试 2.2.3. 安全性与访问控制测试 2.3. 测试工具 3. 测试技术 4. 测试资源 4.1. 人员安排 4.2. 测试环境 4.2.…...
在MySQL中执行sum case when报错：SUM does not exist
1. 报错 在pgsql中能正常运行的一段SQL在MySQL中运行的时候报错了： SELECT DATE( hr.handle_time ) AS statsDate,SUM ( CASE WHEN hma.app_type IN ( 2, 5 ) THEN ch_money ELSE 0 END ) AS aliPayAmt,SUM ( CASE WHEN hma.app_type IN ( 1, 4 ) THEN ch_money EL…...
SQL面试题——日期交叉问题 合并日期重叠的活动
日期交叉问题—合并日期重叠的活动 今天的需求背景和前面我们的一个面试题目的背景一样，只不过是具体的需求变了，可以先看一下我们之前的文章SQL面试题——日期交叉问题 计算活动的总天数 +------+----------+----------+ | id| stt| ett| +------+--------…...
科普文：一文搞懂Postman
1. 概叙 1.1 Postman简介 Postman是一款强大的接口测试工具，主要用于测试HTTP请求，支持各种HTTP请求方法，包括GET、POST、PUT、DELETE等，并且提供了丰富的功能来模拟和测试各种网络请求。 Postman官网上这样介…...
LearnOpenGL学习（模型加载 -- Assimp，网格，模型）
完整代码见：zaizai77/Cherno-OpenGL: OpenGL 小白学习之路 Assimp 3D建模工具如Blender、3DS Max在导出模型文件时，会自动生成所有的顶点坐标、顶点法线和纹理坐标。 .obj 格式只包含了模型数据和材质信息（颜色、贴图等） Assi…...
基于Pyhton的人脸识别（Python 3.12+face_recognition库）
使用Python进行人脸编码和比较 简介 在这个教程中，我们将学习如何使用Python和face_recognition库来加载图像、提取人脸编码，并比较两个人脸是否相似。face_recognition库是一个强大的工具，它基于dlib的深度学习模型，可以轻松实…...
Scala的模式匹配（2）
package hfdobject Test34_2 {//match case匹配元组//能根据元组元素的个数来匹配，不是一一精确的匹配值def main(args: Array[String]): Unit {val d1(1,2,3) // val d1(1,2,3,4) // val d1(1,2,3,4,5)val d:Anyd1 //d的类型是Anyd match {case (x,y,z)>…...
Java 初学者的第一个 SpringBoot 系统
Java 初学者的第一个 SpringBoot 系统 对编程初学者而言，都存在一个 “第一个系统” 的问题。有些学习者找不到自己的 “第一个系统”，他们即使再努力也没有办法了解完整的系统，即使他们把教科书里的所有程序都跑通了。但是，面对…...
java IO面试题
目录 Java IO设计上使用了什么设计模式？ 你怎么理解同步IO和异步IO? 字节流和字符流的区别? Java 流量有多少种类型? 如何将一个 java 将对象序列化到文件中? 如何实现 java 序列化? Filter流是什么? Filter流有哪些可用? 如何实现对象克隆? BIO、…...
Chocolatey软件包管理工具处理MSI升级的原理与实践
Chocolatey软件包管理工具处理MSI升级的原理与实践 在Windows环境下，Chocolatey作为一款强大的包管理工具，其处理MSI（Microsoft Installer）格式软件包升级的机制值得深入探讨。本文将详细介绍Chocolatey如何处理MSI升级ÿ…...
Navicat连接SQL Server及SpringBoot连接SQL Server（jtds）
Navicat连接SQL Server 安装自带的SQL Server客户端 去到Navicat安装目录，找到安装程序，安装即可。 安装对应版本的Microsoft ODBC Driver for SQL Server 打开Navicat输入对应的SQL Server相关信息 然后点测试连接，提示连接成功。 Spr…...
【Git】
博文将不断学习补充 Git下载 将下载链接复制到迅雷中，快速下载 Git安装 保持默认，傻瓜安装即可。 注册Gitee码云，设置公钥 在Git Bash中输入 ssh-keygen -t ed25519 -C "Gitee SSH Key" 找到对应的公钥文件 复制公钥，添…...
HttpServletRequest
HttpServletRequest 类确实是一个封装了完整 HTTP 请求信息的对象，而 Spring MVC 提供了更简化的方式来自动映射请求路径、请求参数等信息到控制器方法中。你不必直接使用 HttpServletRequest 来处理大部分常见的请求内容，因为 Spring MVC 会为你自动处理…...
Apache HttpClient 4和5访问没有有效证书的HTTPS
本文将展示如何配置Apache HttpClient 4和5以支持“接受所有”SSL。 目标很简单——访问没有有效证书的HTTPS URL。 SSLPeerUnverifiedException 在未配置SSL的情况下，尝试消费一个HTTPS URL时会遇到以下测试失败： Test void whenHttpsUrlIsConsumed…...
做异端中的异端 -- Emacs裸奔之路7: 怀念Vim的好
组合键的瑕疵 从Vim切换成Emacs之后，有一明显的不适就是感受Emacs的按键很硬， Vim移动是使用一个按完成的，而Emacs是组合键。 如果向前移动一个字，Vim只要在ESC模式下按w，而Emacs是Alt-f. 特别是当你对键盘改键之后不…...
asp.net core过滤器应用
筛选器类型 授权筛选器 授权过滤器是过滤器管道的第一个被执行的过滤器，用于系统授权。一般不会编写自定义的授权过滤器，而是配置授权策略或编写自定义授权策略。简单举个例子。 using Microsoft.AspNetCore.Authorization; using Microsoft.AspNetCo…...
VideoBooth: Diffusion-based Video Generation with Image Prompts
VideoBooth: Diffusion-based Video Generation with Image Prompts 概括 文章提出了一个视频生成模型VideoBooth，输入一张图片和一个文本提示词，即可输出保持图片中物体且符合文本提示词要求的视频。 方法 粗-细两阶段设计：1）…...
面阵相机的使用和注意事项
引言 面阵相机（Area Scan Camera）是一种广泛应用于工业视觉、医学成像、安防监控以及科研领域的图像采集设备。与线扫相机不同，面阵相机的传感器包含多行像素（例如1280x1024、1920x1080等），能够在一个曝光…...
人工智能与机器学习在智能扭矩系统中的应用
【大家好，我是唐Sun，唐Sun的唐，唐Sun的Sun。】 在当今科技飞速发展的时代，智能扭矩系统正经历着一场深刻的变革，而人工智能（AI）和机器学习算法的应用成为了推动这一变革的关键力量。 传统的扭矩…...
【附源码】基于环信鸿蒙IM SDK实现一个聊天Demo
项目背景 本项目基于环信IM 鸿蒙SDK 打造的鸿蒙IM Demo，完全适配HarmonyOS NEXT系统，实现了发送消息，添加好友等基础功能。代码开源，功能简洁，如果您有类似开发需求可以参考。 源码地址：https://github.c…...
【 AI技术赋能有限元分析与材料科学应用实践】Neo-Hookean 材料与深度学习结合的有限元分析
Neo-Hookean 材料模型是用于描述非线性弹性材料（如软组织和橡胶等）的经典模型，特别适用于大变形问题。其基本思想是通过应变能密度函数来描述材料的弹性行为。在该模型中，材料的应力-应变关系不仅依赖于应变能，还通过变…...
数据分析处理-方法二)
Origin快速拟合荧光寿命、PL Decay (TRPL)数据分析处理-方法二
1.先导入数据到origin 2.导入文件的时候注意：名字短的这个是，或者你打开后看哪个里面有800，因为我的激光重频是1.25Hz（应该是，不太确定单位是KHz还是MHz），所以对应的时间是800s。 3.选中两列直接…...
LeetCode Hot100 51~60
图论51. 岛屿问题52. 腐烂的橘子53. 课程表54. 前缀树55. 全排列56. 子集57. 电话号码58. 组合总和59. 括号生成60. 单词搜索 图论 51. 岛屿问题 经典洪水问题算法 class Solution { public:int numIslands(vector<vector<char>>& grid) {int nr grid.size…...
第一节：ORIN NX介绍与基于sdkmanager的镜像烧录（包含ubuntu文件系统/CUDA/OpenCV/cudnn/TensorRT）
ORIN NX技术参数 Orin NX版本对比 如上图所示，ORIN NX官方发布的版本有两个版本一个版本是70TOPS算力，DDR为8GB的版本低配版本，一个是100TOPS算法，DDR为16GB的高配版本。 Orin NX的外设框图 两个版本除了GPU和DDR的差距外，外设基本上没有区别，丰富的外设接口，后续开发…...
使用Pygame创建一个简单的消消乐游戏
消消乐游戏是一种经典的益智游戏，玩家通过交换相邻的方块来形成三个或更多相同颜色的连续方块，从而消除它们。本文将介绍如何使用Python的Pygame库来创建一个简单的消消乐游戏。 准备工作 在开始之前，请确保已安装Pygame库。可以通过以下命…...
node.js基础学习-JWT登录鉴权（十四）
一、前言 JWT（JSON Web Token）是一种开放标准（RFC 7519），用于在各方之间安全地传输信息。它本质上是一个字符串，由三部分组成：头部（Header）、载荷（Payload&am…...
AbutionGraph-时序向量图谱数据库-快速安装部署
运行环境 1）操作系统 最好是使用CentOS7或者Ubuntu18以上系统，不满足的话请升级系统内核gcc版本至8以上版本。 支持所有国产主流操作系统银河麒麟、统信OS、深度等等，均做过兼容性测试； 2）CPU 为确保数据库每个进…...
翻译质量差对电子课程用户体验的影响
电子学习改变了教育交付方式，使全球不同受众更容易获得课程。然而，随着这种学习模式的发展，对周到地本地化和翻译的需求也在增长。如果做得好，翻译可以弥合文化和语言分歧，创造无缝和包容的学习体验。然而，…...
PS的功能学习（修复、画笔）
混合器画笔工具 就像，电子毛笔 关键功能有两个，自带一个混合器色板 清理画笔是全清，换一支新的毛笔，执行完之后在判断是否载入画笔 载入画笔就是把前景色上的颜色进行叠加处理，重新混入当前的混合色 （…...
Android 使用 Canvas 和 Paint 实现圆形图片
学习笔记 效果展示: 全部代码: public class YuanActivity extends AppCompatActivity {private ActivityYuanBinding binding;Overrideprotected void onCreate(Bundle savedInstanceState) {super.onCreate(savedInstanceState);// 通过 DataBinding 获取布局文件binding …...
vxe-table 键盘操作，设置按键编辑方式，支持覆盖方式与追加方式
vxe-table 全键盘操作，按键编辑方式设置，覆盖方式与追加方式； 通过 keyboard-config.editMode 设置按键编辑方式；支持覆盖方式编辑和追加方式编辑 安装 npm install vxe-pc-ui4.3.15 vxe-table4.9.15// ... import VxeUI from v…...
BUUCTF Pwn [HarekazeCTF2019]baby_rop 题解
下载 checksec 64位 用IDA64打开 定位main函数 栈溢出漏洞 SHIFTF12的字符串看到了binsh 以及函数窗口有system 因为是64位 找到rdi传参和ret栈平衡 构造exp： from pwn import *#p process(./babyrop) p remote("node5.buuoj.cn", 27869)addr_prr 0…...
什么是封装性？C++ 中如何实现封装？封装性的好处是什么？
一、引言 在面向对象编程中，封装性是一个重要的概念。封装可以帮助我们更好地组织和管理代码，提高代码的可维护性、可扩展性和安全性。本文将详细介绍什么是封装性，C 中如何实现封装以及封装性的好处。 二、什么是封装性？ 封装…...
【MySQL】[42000][1071] Specified key was too long； max key length is 3072 bytes
问题描述 创建表时发生错误。 create table if not exists tbl_user(id int unsigned auto_increment comment 用户IDprimary key,username varchar(1023) not null comment 用户名,password varchar(1023) default 123456 …...
人工智能驱动的骗局会模仿熟悉的声音
由于人工智能技术的进步，各种现代骗局变得越来越复杂。 这些骗局现在包括人工智能驱动的网络钓鱼技术，即使用人工智能模仿家人或朋友的声音和视频。 诈骗者使用来自社交媒体的内容来制作深度伪造内容，要求提供金钱或个人信息。个人应该通过…...
实数与复数频谱掩蔽在音频分离中的应用
使用实数和复数频谱掩蔽进行音频分离 频谱掩蔽是指在音频信号的频谱表示中，通过选择性地增强或抑制某些频率成分来改善信号质量或实现信号分离的技术。频谱掩蔽可以分为两种类型：实数掩蔽和复数掩蔽。 实数频谱掩蔽 实数频谱掩蔽主要关注音频信号的幅…...
C++算法练习-day62——491.非递减子序列
题目来源：. - 力扣（LeetCode） 题目思路分析 这个问题要求找出数组 nums 中的所有非严格递增子序列，其中每个子序列至少包含两个元素。非严格递增子序列意味着子序列中的元素可以相等，但不允许递减。 为了解决这个问…...
golang实现单例日志对象
原文地址：golang实现单例日志对象 – 无敌牛 欢迎参观我的个人博客：无敌牛 – 技术/著作/典籍/分享等 介绍 golang有很多日志包，通过设置和修改都能实现日志轮转和自定义日志格式。例如：log、zap、golog、slog、log4go 等等。 …...
Redis——个人笔记留存
今日内容 1. redis1. 概念2. 下载安装3. 命令操作1. 数据结构4. 持久化操作5. 使用Java客户端操作redis Redis 1. 概念： redis是一款高性能的NOSQL系列的非关系型数据库 1.1.什么是NOSQLNoSQL(NoSQL Not Only SQL)，意即“不仅仅是SQL”，是…...
c# Grpc取消
net6.0 通过CancellationTokenSource 客户端取消Grpc，服务端判断 IsCancellationRequested 是否取消。 proto: syntax "proto3";// 引用可空类型 import "google/protobuf/wrappers.proto";option csharp_namespace "Grpc.Common"…...
Flask 是什么？
近期开发chatbot 程序，过程中要使用Flask，所以收集资料记录这个套件的信息： Flask 是什么？ Flask 是一个轻量级、模块化的 Python Web 框架，用于构建 Web 应用程序和 API。它被设计为简单、灵活且可扩展，…...
智能合约
06-智能合约 0 啥是智能合约？ 定义 智能合约，又称加密合约，在一定条件下可直接控制数字货币或资产在各方之间转移的一种计算机程序。 角色 区块链网络可视为一个分布式存储服务，因为它存储了所有交易和智能合约的状态 智能合约还…...
【机器学习】分类器
在机器学习(Machine Learning，ML)中，分类器泛指算法或模型，用于将输入数据分为不同的类别或标签。分类器是监督学习的一部分，它依据已知的数据集中的特征和标签进行训练，并根据这些学习到的知识对新的未标记数据进行分…...
ASP 快速参考
ASP 快速参考 概述 ASP（Active Server Pages）是一种由微软开发的服务器端脚本环境，用于动态生成交互性网页。它允许开发者结合HTML、VBScript或JScript脚本语言来创建和运行动态网页或Web应用程序。本快速参考将提供ASP的基础知识、常用内置…...
支持向量机算法：原理、实现与应用
摘要： 本文深入探讨支持向量机（Support Vector Machine，SVM）算法，详细阐述其原理、数学模型、核函数机制以及在分类和回归问题中的应用方式。通过以 Python 和 C# 为例，展示 SVM 算法在不同编程环境下的具体…...
蓝桥杯分治
P1226 【模板】快速幂 题目描述 给你三个整数 𝑎,𝑏,𝑝a,b,p，求 𝑎𝑏 mod 𝑝abmodp。 输入格式 输入只有一行三个整数，分别代表 𝑎,𝑏,𝑝a,b,p。…...
群控系统服务端开发模式-应用开发-邮件工厂结构封装
首先在系统根目录下extend文件夹下创建邮件工厂文件夹并更名叫Mail。 一、邮件发送父类 在Mail目录下创建邮件发送父类并更名为MailSenderInterface.php，代码如下 <?php /*** 邮件发送父类* User: 龙哥三年风水* Date: 2024/12/5* Time: 14:22*/ namespace Ma…...
COCO数据集理解
COCO（Common Objects in Context）数据集是一个用于计算机视觉研究的广泛使用的数据集，特别是在物体检测、分割和图像标注等任务中。COCO数据集由微软研究院开发，其主要特点包括： 丰富的标签：COCO数据集包含…...