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

devtools/2024/11/13 8:08:35/

给你两个正整数 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.ppmy.cn/devtools/132808.html

相关文章

TikTok Spark Ads火花广告创建及相关要点

TikTok的广告类型多样、功能各异&#xff0c;如果你需要投放精准度更高、效果更持久、更能吸引用户点击和参与的广告&#xff0c;那么Spark Ads会是一个相当不错的选择。 一、什么是TikTok Spark Ads 1.概念 Spark Ads是直接使用真实的自然流量视频及其功能来进行宣传的一种原…

MeterSphere接口自动化-ForEach循环

接口自动化场景&#xff1a;一个接口根据不同的参数取值来运行测试&#xff0c;本场景中只有一个参数来去不同值。举例如下&#xff1a; https:://test.csdn/query?placementList1接口&#xff0c;测试id1,2,3时&#xff0c;断言接口返回的data数据都有返回。&#xff08;当然…

Chrome与火狐哪个浏览器的移动版本更流畅

在当今的数字化时代&#xff0c;移动设备已经成为我们生活中不可或缺的一部分。而浏览器作为我们访问互联网的重要工具&#xff0c;其性能和用户体验直接影响到我们的使用感受。本文将对比Chrome和火狐&#xff08;Firefox&#xff09;两款主流浏览器的移动版本&#xff0c;探讨…

CSS外边距合并及解决办法

在CSS中&#xff0c;外边距合并&#xff08;Margin Collapsing&#xff09;是一种当两个或多个元素的垂直外边距相遇时&#xff0c;它们合并成一个外边距的现象。这个合并后的外边距的大小等于两个外边距中较大的那个&#xff0c;或者在某些情况下&#xff0c;等于它们之和。外…

高级 <HarmonyOS主题课>构建华为支付服务的课后习题

五色令人目盲&#xff1b; 五音令人耳聋&#xff1b; 五味令人口爽&#xff1b; 驰骋畋猎&#xff0c;令人心发狂&#xff1b; 难得之货&#xff0c;令人行妨&#xff1b; 是以圣人为腹不为目&#xff0c;故去彼取此。 本篇内容主要来自&#xff1a;<HarmonyOS主题课>构建…

【模拟集成电路】知识点笔记_1

知识点笔记_1 零极点相关1 PM和GM相关概念2零极点 温度系数五种常见噪声源MOS管和BJT选取BJT刨面图工艺角衬底主要噪声来源共模反馈三种常用CMFB1 工作在线性区MOS作为CMFB&#xff08;匹配决定输出电压&#xff09;2 电阻反馈&#xff08;Buf&#xff09;3 电流差分对&#xf…

ffmpeg命令——从wireshark包中的rtp包中分离h264

ffmpeg命令——从wireshark包中的rtp包中分离h264 过滤 RTP打开wireshark的RTP 播放器选中流并导出荷载使用 ffmpeg 命令行分离出 h264 过滤 RTP 打开wireshark的RTP 播放器 选中流并导出荷载 使用 ffmpeg 命令行分离出 h264 ffmpeg -i test.raw -vcodec copy -an -f h264 tes…

软考:论运维

运维是什么&#xff1f; 运维是指软件运行上线后&#xff0c;对应用程序进行的一系列维护和管理活动。系统的维护、监控和管理。 为什么要运维&#xff1f; 运维的目的是确保应用程序的稳定运行、性能优化和安全防护。运维的范围非常广泛&#xff0c;包括硬件、软件、网络和安…