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