给你两个正整数 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)