今日力扣:3235. 判断矩形的两个角落是否可达

给你两个正整数 xCorner 和 yCorner 和一个二维整数数组 circles ,其中 circles[i] = [xi, yi, ri] 表示一个圆心在 (xi, yi) 半径为 ri 的圆。

坐标平面内有一个左下角在原点,右上角在 (xCorner, yCorner) 的矩形。你需要判断是否存在一条从左下角到右上角的路径满足:路径 完全 在矩形内部,不会 触碰或者经过 任何 圆的内部和边界,同时  在起点和终点接触到矩形。

如果存在这样的路径,请你返回 true ,否则返回 false 。

class Solution:def canReachCorner(self, X: int, Y: int, circles: List[List[int]]) -> bool:# 判断点 (x,y) 是否在圆 (ox,oy,r) 内def in_circle(ox: int, oy: int, r: int, x: int, y: int) -> bool:return (ox - x) * (ox - x) + (oy - y) * (oy - y) <= r * rvis = [False] * len(circles)def dfs(i: int) -> bool:x1, y1, r1 = circles[i]# 圆 i 是否与矩形右边界/下边界相交相切if y1 <= Y and abs(x1 - X) <= r1 or \x1 <= X and y1 <= r1 or \x1 > X and in_circle(x1, y1, r1, X, 0):return Truevis[i] = Truefor j, (x2, y2, r2) in enumerate(circles):# 在两圆相交相切的前提下,点 A 是否严格在矩形内if not vis[j] and \(x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= (r1 + r2) * (r1 + r2) and \x1 * r2 + x2 * r1 < (r1 + r2) * X and \y1 * r2 + y2 * r1 < (r1 + r2) * Y and \dfs(j):return Truereturn Falsefor i, (x, y, r) in enumerate(circles):# 圆 i 包含矩形左下角 or# 圆 i 包含矩形右上角 or# 圆 i 与矩形上边界/左边界相交相切if in_circle(x, y, r, 0, 0) or \in_circle(x, y, r, X, Y) or \not vis[i] and (x <= X and abs(y - Y) <= r ory <= Y and x <= r ory > Y and in_circle(x, y, r, 0, Y)) and dfs(i):return Falsereturn True

怎么判断呢?

首先考虑圆心都在矩形内部的情况。如果圆和圆相交或相切,则相当于在两个圆之间架起了一座桥。如果圆和矩形边界相交或相切,则相当于在矩形边界和圆之间架起了一座桥。如果可以从矩形【上边界/左边界】通过桥到达矩形【右边界/下边界】,则说明路被堵死,无法从矩形左下角移动到矩形右上角。

也可以把桥理解成切割线,如果能把从矩形左下角到矩形右上角的路径切断,则无法从矩形左下角移动到矩形右上角。

用图论的术语来说,就是把圆抽象成节点,在相交或相切的节点之间连边,得到一张无向图。如果从与【上边界/左边界】相交的节点出发,DFS 这张图,到达与【右边界/下边界】相交的节点,则说明无法从矩形左下角移动到矩形右上角。

作者:灵茶山艾府
链接:https://leetcode.cn/problems/check-if-the-rectangle-corner-is-reachable/solutions/2860214/deng-jie-zhuan-huan-bing-cha-ji-pythonja-yf9y/
来源:力扣(LeetCode)
 

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

HCIP-HarmonyOS Application Developer 习题(二十)

1、&#xff08;判断题&#xff09;在使用 EventHandler 实现线程问通信时如果 EventRurner取出的是InnerEvent事件&#xff0c;则 EventRunner 会直接在新线程上处理该事件。 答案&#xff1a;错误 分析&#xff1a;如果EventRunner取出的事件为InnerEvent事件&#xff0c;则触…

恭喜!2024年度大连市科技人才创新、科技人才创业项目拟立项公示!

精选SCI/SSCI/EI SCI&EI ●IEEE 1区TOP 计算机类&#xff08;含CCF&#xff09;&#xff1b; ●EI快刊&#xff1a;最快1周录用&#xff01; 知网(CNKI)、谷歌学术期刊 ●7天录用-检索&#xff08;100%录用&#xff09;&#xff0c;1周上线&#xff1b; 免费稿件评估 …

CSS3中动画的使用animation

1.基本使用 2.其他属性 3.复合属性

C语言多维数组抽象理解:切格子思维

其实早在两年前我就写过一篇关于多维数组的文章&#xff1a;详解多维数组与指针之间的关系&#xff0c;随着时间的推移&#xff0c;我的工作与学习逐渐深入&#xff0c;对C语言有了更深入的理解&#xff0c;觉得之前写的文章里关于多维数组部分有些复杂&#xff0c;不能以最简单…

超越Axure:探索新一代原型设计工具

Axure RP是一款被广泛认可的快速原型设计工具&#xff0c;专为专业设计师打造&#xff0c;用于创建高效的产品原型图&#xff0c;包括APP和网页的原型图、框架图和结构图等。Axure RP制作的原型图能够实现与实际APP相似的交互效果&#xff0c;便于向用户或客户展示&#xff0c;…

PVE纵览-从零开始:了解Proxmox Virtual Environment

PVE纵览-从零开始&#xff1a;了解Proxmox Virtual Environment 文章目录 PVE纵览-从零开始&#xff1a;了解Proxmox Virtual Environment摘要引言什么是Proxmox Virtual EnvironmentPVE的核心功能PVE 优势如何开始使用PVEPVE应用案例总结 关键字&#xff1a; PVE、 虚拟机、…

装杯 之 Linux指令【补充篇】

“生活就像海洋&#xff0c;只有意志坚强的人&#xff0c;才能到达彼岸” ---马克思 目录 1.grep指令 ​编辑 2.zip/unzip指令 3.tar指令&#xff08;重要&#xff09;&#xff1a;打包/解包&#xff0c;不打开它&#xff0c;直接看内容 4.bc指令 5.uname 指令 1.grep…

AI自动直播软件之直播任务模块开发!

AI自动直播软件&#xff0c;作为现代科技与传统直播行业的完美结合&#xff0c;正在逐步改变我们的生活方式&#xff0c;它不仅能够帮助主播们实现24小时不间断的直播&#xff0c;还能通过智能算法分析观众喜好&#xff0c;推送定制化的内容&#xff0c;极大地提升了用户体验。…

windows工具 -- 开源图片查看器ImageClass

目的 windows自带的图像查看有些不好用 ImageClass效果 下载安装 点击下载 ImageClass https://imageglass.org/releases 双击安装即可 如果想要和一样的布局可以参考 下图布局设置: 其他功能自行探索一下, 功能很丰富

99_api_intro_websitetools_dnslookup

域名 DNS 信息查询 API 数据接口 网络工具&#xff0c;多种记录类型数据返回&#xff0c;丰富的信息结构&#xff0c;毫秒级响应。 1. 产品功能 提供域名 DNS 解析完整记录&#xff1b;丰富的解析记录类型&#xff0c;包括&#xff1a;A, AAAA, MX, TXT, NS, CNAME, SRV, PTR, …

Intern大模型训练营(五):书生大模型全链路开源体系笔记

观看视频&#xff0c;可以比较详细地了解到书生大模型全链路开源体系。 其中有几个印象比较深的点&#xff1a; 这张图讲述了书生浦语大模型开源的发展史&#xff0c;同时与主流的llama和Chatgpt模型进行比较&#xff0c;可以看出在参数上&#xff0c;InterLM在努力追赶甚至超…

ONLYOFFICE 8.2 版:助力自动化办公的佼佼者

0. 引言 在当今数字化办公的浪潮中&#xff0c;办公软件的选择对于提高工作效率和质量至关重要。就像在算法的世界里&#xff0c;合适的算法能高效地解决问题一样&#xff0c;一款优秀的办公软件能为我们的办公流程带来前所未有的便捷。ONLYOFFICE 8.2 版的出现&#xff0c;为…

03集合基础

目录 1.集合 Collection Map 常用集合 List 接口及其实现 Set 接口及其实现 Map 接口及其实现 Queue 接口及其实现 Deque 接口及其实现 Stack类 并发集合类 工具类 2.ArrayList 3.LinkedList 单向链表的实现 1. 节点类&#xff08;Node&#xff09; 2. 链表类&a…

6KBhtm+js实现提交名单随机抽取功能适用活动或课堂随机点名

<!DOCTYPE html> <html lang"zh"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <title>名单抽奖系统</title> <style> *{ma…

面向对象的需求分析和设计(一)

[toc] 1. 引言 前一篇文章《我对需求分析的理解》提到了面向对象分析和设计&#xff0c;正好最近又重新有重点的读了谭云杰著的《Think in UML》&#xff0c;感觉有必要写把书中一些核心内容观点以及自己的想法整理出来&#xff0c;一是方便自己日后的复习&#xff0c;另外也…

树的存储结构-树,二叉树,森林的相互转换

双亲表示法存储树 优点:查找指定结点的双亲十分方便 缺点:查指定结点的孩子只能从头遍历 插入操作:插入对位无须按照某种顺序 删除操作1:将指定结点的parent数据赋值为-1表示为空(删除节点为叶子节点) 删除操作2:将最后一个数据覆盖到指定结点的数据域(删除节点为叶子节点…

OpenGL学习笔记(四) RGBA颜色

RGBA模式中&#xff0c;每一个像素会保存以下数据&#xff1a;R值&#xff08;红色分量&#xff09;、G值&#xff08;绿色分量&#xff09;、B值&#xff08;蓝色分量&#xff09;和A值&#xff08;alpha分量&#xff09;。其中红、绿、蓝三种颜色相组合&#xff0c;就可以得到…

机器学习2_支持向量机_线性可分——MOOC

目录 定义 线性可分&#xff08;Linear Separable&#xff09; 线性不可分&#xff08;Nonlinear Separable&#xff09; 数学化定义 问题描述 优化问题 线性可分定义 假定训练样本集是线性可分的 1、最小化&#xff08;Minimize&#xff09;&#xff1a; 2、限制条件…

零基础学习Spring AI Java AI使用向量数据库postgresql 检索增强生成 RAG

零基础学习Spring AI Java AI使用向量数据库postgresql 检索增强生成 RAG 向量数据库是一种特殊类型的数据库&#xff0c;在人工智能应用中发挥着至关重要的作用。 在向量数据库中&#xff0c;查询与传统的关系数据库不同。它们不是进行精确匹配&#xff0c;而是执行相似性搜…

口子查好做吗?有什么特点?

大家好&#xff0c;我是橙河老师&#xff0c;一家问卷公司老板&#xff0c;今天讲一讲“口子查好做吗&#xff1f;有什么特点&#xff1f;” 1.口子查是公开性资源&#xff0c;由国外问卷公司直接发布在主流的平台上&#xff0c;比如我们的抖音、百度这些平台&#xff0c;竞争…