<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>

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

        def getTouch(circle):
            x,y, r = circle
            found = [False]*4

            if x+r>=X or x-r<=0 or y+r>=y or  y-r<=0:
                if x+r>=X :
                    found[3] = True
                if x-r<=0 :
                    found[0] = True
                if y+r>=Y :
                    found[2] = True
                if y-r<=0:
                    found[1] = True
            return found
        
        def check(found):
            ret = True
            for i in found:
                ret &= i
            return ret or (found[2]&found[3]) or (found[0]&found[1]) or (found[0]&found[3]) or (found[1]&found[2])
        
        def isTouch(found):
            ret = False
            for i in found:
                ret |= i
            return ret


        
        def isIntersectCircle(c1,c2):
            x1,y1,r1 =c1
            x2,y2,r2 =c2
            yd = (y1-y2)**2
            xd = (x1-x2)**2
            r= (r1+r2)**2
            return yd+xd<=r


        s=set()

        for start in circles:
            if tuple(start) in s:
                continue 
            q= deque()
            q.append(tuple(start))
            mainFound = getTouch(start)
            while q:
                #print(q)
                c1 = q.popleft()
                if c1 in s:
                    continue

                if check(mainFound):
                    return False

                s.add(tuple(c1))
                for c2 in circles:
                    if tuple(c2) in s:
                        continue
                    if isIntersectCircle(c1,c2):
                        #print(c2)
                        f2 = getTouch(c2)
                        #print(f2)
                        for i in range(4):
                            mainFound[i]|= f2[i]
                        
                        if check(mainFound):
                            return False
                        q.append(tuple(c2))

            #print(mainFound, start)

        return True




49578