<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 connected(c1, c2, check_center_in_rect=True):
            x, y, r = c1
            x2, y2, r2 = c2
            if check_center_in_rect:
                # intersection must be in rect
                x3 = x + x2
                y3 = y + y2
                if x3 / 2 > X or y3 / 2 > Y:
                    return False
            dist = (x2 - x) ** 2 + (y2 - y) ** 2
            return (r2 + r) ** 2 >= dist
        graph = [list() for _ in range(len(circles))]
        for i in range(len(circles)):
            for j in range(i + 1, len(circles)):
                if connected(circles[i], circles[j]):
                    # print("here")
                    graph[i].append(j)
                    graph[j].append(i)
        # print(graph)
        visited = [False] * len(circles)
        for i in range(len(circles)):
            stack = [i]
            left, right, up, down = False, False, False, False
            while stack:
                cur = stack.pop()
                if visited[cur]:
                    continue
                visited[cur] = True
                x, y, r = circles[cur]
                flag = True
                if x > X and y > Y:
                    if (x - X) ** 2 + (y - Y) ** 2 > r ** 2:
                        flag = False
                # print(x, X, y, Y, r)
                if x - X >= r:
                    continue
                if y - Y >= r:
                    continue
                if not flag:
                    continue 
                if 0 <= y <= Y and x - r <= 0:
                    left = True
                if 0 <= y <= Y and x + r >= X:
                    right = True
                if 0 <= x <= X and y - r <= 0:
                    down = True
                if 0 <= x <= X and y + r >= Y:
                    up = True
                if connected(circles[cur], (X, 0, 0), False):
                    right, down = True, True
                if connected(circles[cur], (0, Y, 0), False):
                    left, up = True, True
                if connected(circles[cur], (X, Y, 0), False):
                    right, up = True, True
                for nextNode in graph[cur]:
                    stack.append(nextNode)
                # print(stack, visited, left, right, down, up)
            if left and right:
                return False
            if up and down:
                return False
            if left and down:
                return False
            if up and right:
                return False
        return True
                
45046