<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 intersect(c1, c2):
            x1, y1, r1 = c1
            x2, y2, r2 = c2
            return (x2 - x1)**2 + (y2 - y1)**2 <= (r1 + r2)**2
        
        def boxTouches(c):
            # 0b1111
            # left, top, right, bottom
            xi, yi, ri = c
            touches = 0b0
            if xi - ri <= 0:
                touches |= 0b1000
            if xi + ri >= X:
                touches |= 0b0010
            if yi - ri <= 0:
                touches |= 0b0001
            if yi + ri >= Y:
                touches |= 0b0100
            return touches
        
        def blocksPath(touch):
            bl = 0b1001
            tr = 0b0110
            lr = 0b1010
            tb = 0b0101
            return (touch & bl == bl) or (touch & tr == tr) or (touch & lr == lr) or (touch & tb == tb)
        
        n = len(circles)

        # create adjacency matrix of circles that are intersecting each other, as well as the edge of the box
        edges = dict()
        touches = []
        for i in range(n):
            t = boxTouches(circles[i])
            if blocksPath(t):
                return False
            touches.append(t)
            for j in range(i + 1, n):
                if intersect(circles[i], circles[j]):
                    if i not in edges:
                        edges[i] = []
                    if j not in edges:
                        edges[j] = []
                    edges[i].append(j)
                    edges[j].append(i)
        
        seen = set()
        for i in range(n):
            # start with a circle intersecting the edge of the rectangle
            if i not in seen:
                # bfs across intersecting circles, marking circles seen as we hit them
                s = [i]
                all_touches = touches[i]
                while len(s) > 0:
                    curr = s.pop()
                    if curr in seen: continue
                    seen.add(curr)
                    all_touches |= touches[curr]
                    # if reach another edge on the rectangle, then return false
                    if blocksPath(all_touches):
                        return False
                    # otherwise, keep going
                    if curr in edges:
                        for e in edges[curr]:
                            if e not in seen:
                                s.append(e)
        return True
45953