3235. 判断矩形的两个角落是否可达

力扣刷题记录

dfs 困难

3235. 判断矩形的两个角落是否可达

思路

这题还是不会写，直接看的题解，对题解写的做了笔记，在代码中

首先判断起点 终点是否在圆里面
然后判断圆是否与左或上相交，相交后 判断是否和 右或下 相交， 不相交 寻找其它的圆

代码

class Solution:def canReachCorner(self, xCorner: int, yCorner: int, circles: List[List[int]]) -> bool:def pointInCircle(px: int, py: int, x: int, y: int, r: int) -> bool:# 判断点是否在圆里面return (x - px) ** 2 + (y - py) ** 2 <= r ** 2def circleIntersectsTopLeftOfRectangle(x: int, y: int, r: int, xCorner: int, yCorner: int) -> bool:# 圆是否与左 或 上 边界相交return (abs(x) <= r and 0 <= y <= yCorner) or (0 <= x <= xCorner and abs(y - yCorner) <= r) or pointInCircle(x, y, 0, yCorner, r)def circleIntersectsBottomRightOfRectangle(x: int, y: int, r: int, xCorner: int, yCorner: int) -> bool:# 圆是否与右 或 下 边界相交return (abs(y) <= r and 0 <= x <= xCorner) or (0 <= y <= yCorner and abs(x - xCorner) <= r) or (pointInCircle(x, y, xCorner, 0, r))def circlesIntersectInRectangle(x1: int, y1: int, r1: int, x2: int, y2: int, r2: int, xCorner: int, yCorner: int) -> bool:# 两个圆 相交 且圆心之间的一点 位于矩形内部return (x1 - x2) ** 2 + (y1 - y2) ** 2 <= (r1 + r2) ** 2 and x1 * r2 + x2 * r1 < (r1 + r2) * xCorner and y1 * r2 + y2 * r1 < (r1 + r2) * yCornervisited = [False] * len(circles)def dfs(i: int) -> bool:x1, y1, r1 = circles[i]if circleIntersectsBottomRightOfRectangle(x1, y1, r1, xCorner, yCorner):# 当前圆 同时也与 右或者下相交 直接退出 返回无法取得即可return Truevisited[i] = Truefor j, (x2, y2, r2) in enumerate(circles):if (not visited[j]) and circlesIntersectInRectangle(x1, y1, r1, x2, y2, r2, xCorner, yCorner) and dfs(j):# 当前圆已经与左边界或者上边界相交了   继续判断其它圆是否与这个圆 j 相交在矩形里面   满足则继续dfs j 判断圆j是否与矩形 右 下 相交  满足 则说明形成了封闭的# 否则 继续判断其它的圆 一个一个遍历return Truereturn Falsefor i, (x, y, r) in enumerate(circles):if pointInCircle(0, 0, x, y, r) or pointInCircle(xCorner, yCorner, x, y, r):# 起点 终点 在圆里面return Falseif (not visited[i]) and circleIntersectsTopLeftOfRectangle(x, y, r, xCorner, yCorner) and dfs(i):# 不访问重复的圆  判断圆 i 是否与左 或 上 边界相交  然后dfs遍历其它的圆# 好像是 首先找到一个与左或者上相交的圆 如果找到 进入dfs 是否与 矩形 右下相交return Falsereturn True

时间复杂度：O(n^2)
空间复杂度：O(n)