<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 typing import List



import math

# Function to check if two circles touch each other
def intersect(x1, y1, x2, y2, r1, r2):
    d = math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))

    if(d <= r1 - r2):
        return True
    elif(d <= r2 - r1):
        return True
    elif(d < r1 + r2):
        return True
    elif(d == r1 + r2):
        return True
    else:
        return False

import collections
class Solution:
    def canReachCorner(self, X: int, Y: int, circles: List[List[int]]) -> bool:
        a = circles

        up = [False for i in a]
        down = [False for i in a]
        left = [False for i in a]
        right = [False for i in a]
        parent = [i for i in range(len(a))]
        processed = [False for i in a]
        q = collections.deque()

        for i in range(len(a)):
            x,y,r = a[i]

            if x+r>=X:
                right[i]=True
            if x-r<=0:
                left[i]=True
            if y+r>=Y:
                up[i]=True
            if y-r<=0:
                down[i]=True

            if up[i] or down[i] or left[i] or right[i]:
                q.append(i)
                #processed[i]=True

        if len(q)==0:
            return True

        while len(q)>0:
            current_index = q[0]
            if processed[current_index]:
                q.popleft()
                continue
            processed[current_index]=True
            x,y,r = a[q[0]]
            q.popleft()
            parent_of_this = current_index
            while parent_of_this!=parent[parent_of_this]:
                parent_of_this = parent[parent_of_this]
            for i in range(len(a)):
                if processed[i]==False:
                    x2,y2,r2 = a[i]
                    if intersect(x,y,x2,y2,r,r2):
                        parenti = i
                        while parenti != parent[parenti]:
                            parenti = parent[parenti]



                        f = parent_of_this
                        g = parenti
                        up[f]|=up[g]
                        down[f]|=down[g]
                        left[f]|=left[g]
                        right[f]|=right[g]

                        parent[parenti]=parent_of_this

                        q.append(i)

        for i in range(len(a)):
            if up[i] and down[i]:
                return False
            if left[i] and right[i]:
                return False
            if up[i] and right[i]:
                return False
            if down[i] and left[i]:
                return False

        return True
32359