<p>You are given two positive integers <code>xCorner</code> and <code>yCorner</code>, and a 2D array <code>circles</code>, where <code>circles[i] = [x<sub>i</sub>, y<sub>i</sub>, r<sub>i</sub>]</code> denotes a circle with center at <code>(x<sub>i</sub>, y<sub>i</sub>)</code> and radius <code>r<sub>i</sub></code>.</p>

<p>There is a rectangle in the coordinate plane with its bottom left corner at the origin and top right corner at the coordinate <code>(xCorner, yCorner)</code>. You need to check whether there is a path from the bottom left corner to the top right corner such that the <strong>entire path</strong> lies inside the rectangle, <strong>does not</strong> touch or lie inside <strong>any</strong> circle, and touches the rectangle <strong>only</strong> at the two corners.</p>

<p>Return <code>true</code> if such a path exists, and <code>false</code> otherwise.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">xCorner = 3, yCorner = 4, circles = [[2,1,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/18/example2circle1.png" style="width: 346px; height: 264px;" /></p>

<p>The black curve shows a possible path between <code>(0, 0)</code> and <code>(3, 4)</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">xCorner = 3, yCorner = 3, circles = [[1,1,2]]</span></p>

<p><strong>Output:</strong> <span class="example-io">false</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/18/example1circle.png" style="width: 346px; height: 264px;" /></p>

<p>No path exists from <code>(0, 0)</code> to <code>(3, 3)</code>.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">xCorner = 3, yCorner = 3, circles = [[2,1,1],[1,2,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">false</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/18/example0circle.png" style="width: 346px; height: 264px;" /></p>

<p>No path exists from <code>(0, 0)</code> to <code>(3, 3)</code>.</p>
</div>

<p><strong class="example">Example 4:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">xCorner = 4, yCorner = 4, circles = [[5,5,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/08/04/rectangles.png" style="width: 346px; height: 264px;" /></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= xCorner, yCorner &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= circles.length &lt;= 1000</code></li>
	<li><code>circles[i].length == 3</code></li>
	<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub>, r<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
</ul>

from collections import defaultdict
import math
class Solution(object):
    def canReachCorner(self, X, Y, circles):
        """
        :type X: int
        :type Y: int
        :type circles: List[List[int]]
        :rtype: bool
        """
        original_circles = list(circles)

        def reacheable(min_x, min_y, max_x, max_y):
            bottom_reachable = min_y <= 0 and max_y >= 0 and min_x <= X and max_x >= 0
            left_reachable = min_x <= 0 and max_x >= 0 and min_y <= Y and max_y >= 0
            top_reachable = min_y <= Y and max_y >= Y and min_x <= X and max_x >= 0
            right_reachable = min_x <= X and max_x >= X and min_y <= Y and max_y >= 0
            if (bottom_reachable and left_reachable) \
                or (bottom_reachable and top_reachable) \
                    or (left_reachable and right_reachable) \
                        or top_reachable and right_reachable:
                return False
            return True

        def is_overalapping(i, j):
            circle1 = original_circles[i]
            circle2 = original_circles[j]
            c1c2 = math.sqrt( (circle1[0]-circle2[0])**2 + (circle1[1]-circle2[1])**2)
            if c1c2 <= abs( circle1[2]-circle2[2]) \
                    or c1c2 <= circle1[2]+circle2[2]:
                return True
            return False
        
        min_x, min_y, max_x, max_y = float('inf'), float('inf'), float('-inf'), float('-inf')
        def dfs(node):
            nonlocal min_x, min_y, max_x, max_y
            visited[node] = 1
            min_x = min(min_x, circles[node][0])
            max_x = max(max_x, circles[node][1])
            min_y = min(min_y, circles[node][2])
            max_y = max(max_y, circles[node][3])

            for child in parent_map[node]:
                if visited[child] == 0:
                    dfs(child)

            
        for i in range(len(circles)):
            x, y, r = circles[i]
            circles[i] = [x-r, x+r, y-r, y+r]

        parent = [i for i in range(len(circles))]

        def find_parent(i):
            while i != parent[i]:
                i = parent[i]
            return parent[i]

        def union(i, j):
            parent_i = find_parent(i)
            parent_j = find_parent(j)
            if parent_i < parent_j:
                parent[parent_j] = parent_i
            elif parent_i > parent_j:
                parent[parent_i] = parent_j

        for i in range(len(circles)):
            for j in range(i+1, len(circles)):
                if is_overalapping(i, j):
                    union(i, j)

        parent_map = defaultdict(list)
        for i in range(len(parent)):
            parent_map[parent[i]].append(i)
        
        visited = [0]*len(parent)
        for i in range(len(parent)):
            min_x, min_y, max_x, max_y = float('inf'), float('inf'), float('-inf'), float('-inf')
            if visited[i] == 0:
                dfs(i)
                # print(min_x, min_y, max_x, max_y)
                if reacheable(min_x, min_y, max_x, max_y) == False:
                    return False
        return True
18765