力扣21 打卡16 判断矩形的两个角落是否可达

思路：

首先，检查矩形的起点和终点是否在任何一个圆的范围内，如果是则不存在合法路径。接着，判断每个圆是否与矩形的左上角边界或右下角边界相交。对于与左上边界相交的圆，使用深度优先搜索（DFS），查找是否存在一组相连的圆，最终能连接到右下边界。若找到这样的路径，则矩形被封锁，返回 False。否则，表示有合法路径存在，返回 True。

from typing import List

class Solution:
    def canReachCorner(self, xCorner: int, yCorner: int, circles: List[List[int]]) -> bool:
        
        # 判断点 (px, py) 是否在圆 (x, y, r) 内
        def pointInCircle(px: int, py: int, x: int, y: int, r: int) -> bool:
            return (x - px) ** 2 + (y - py) ** 2 <= r ** 2

        # 判断圆 (x, y, r) 是否与矩形的左上边界相交
        def 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)

        # 判断圆 (x, y, 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))

        # 判断两个圆 (x1, y1, r1) 和 (x2, y2, r2) 是否在矩形内相交
        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) * yCorner

        # 访问标记数组，记录已经访问过的圆
        visited = [False] * len(circles)

        # 深度优先搜索函数
        def dfs(i: int) -> bool:
            x1, y1, r1 = circles[i]
            if circleIntersectsBottomRightOfRectangle(x1, y1, r1, xCorner, yCorner):
                return True
            visited[i] = True
            for j, (x2, y2, r2) in enumerate(circles):
                if not visited[j] and circlesIntersectInRectangle(x1, y1, r1, x2, y2, r2, xCorner, yCorner) and dfs(j):
                    return True
            return False

        # 主循环
        for i, (x, y, r) in enumerate(circles):
            # 检查起点或终点是否在任何一个圆内
            if pointInCircle(0, 0, x, y, r) or pointInCircle(xCorner, yCorner, x, y, r):
                return False
            # 如果圆与矩形的左上边界相交，并且通过 DFS 搜索找到了与右下角相连的路径，则返回 False
            if not visited[i] and circleIntersectsTopLeftOfRectangle(x, y, r, xCorner, yCorner) and dfs(i):
                return False
        return True