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

class Solution:
    def __init__(self):
        self.graph = None
        self.circle_count = 0
        self.X = 0
        self.Y = 0
    
    def is_intersecting(self, xc, yc, r, edge):
        """
        Check if the circle with center (xc, yc) and radius r intersects with the given edge of the rectangle.
        """
        if edge == 'L':
            return xc <= r
        elif edge == 'R':
            return xc + r >= self.X
        elif edge == 'B':
            return yc <= r
        elif edge == 'T':
            return yc + r >= self.Y
        return False
    def is_intersecting_circles(self, x0,y0,R0, x1,y1,R1):
        return (R0 - R1)**2 <= (x0 - x1)**2 + (y0 - y1)**2 <= (R0 + R1)**2
    def build_graph(self, X, Y, circles):
        """
        Build a graph with vertices representing circles and rectangle edges.
        """
        self.X = X
        self.Y = Y
        self.circle_count = len(circles)
        self.graph = defaultdict(set)
        
        # Nodes representing edges
        edge_indices = {'L': self.circle_count + 3, 'R': self.circle_count + 1, 'B': self.circle_count + 2, 'T': self.circle_count}
        
        # Connect circles to edges they intersect
        for i, (xc, yc, r) in enumerate(circles):
            for edge in ['L', 'R', 'B', 'T']:
                if self.is_intersecting(xc, yc, r, edge):
                    self.graph[i].add(edge_indices[edge])
                    self.graph[edge_indices[edge]].add(i)
        
        # # Connect edges to each other if there's no circle blocking the path
        # edges = ['L', 'R', 'B', 'T']
        # for i, edge1 in enumerate(edges):
        #     for j, edge2 in enumerate(edges):
        #         if i != j and self.are_edges_connected(edge1, edge2, circles):
        #             self.graph[edge_indices[edge1]].add(edge_indices[edge2])
        #             self.graph[edge_indices[edge2]].add(edge_indices[edge1])
        
        
        for i, (xc, yc, r) in enumerate(circles):
            for j, (xcc,ycc,r2) in enumerate(circles):
                if i == j: continue
                if self.is_intersecting_circles(xc, yc, r, xcc,ycc,r2):
                    # print(i,j)
                    self.graph[i].add(j)
                    self.graph[j].add(i)
    def are_edges_connected(self, edge1, edge2, circles):
        """
        Determine if two edges are connected without any circle blocking the path.
        """
        for xc, yc, r in circles:
            if (self.is_intersecting(xc, yc, r, edge1) and
                self.is_intersecting(xc, yc, r, edge2)):
                return False
        return True
    
    def bfs(self, start, target):
        """
        Perform BFS to check if there's a path from start to target.
        """
        visited = set()
        queue = deque([start])
        
        while queue:
            node = queue.popleft()
            if node == target:
                return True
            if node in visited:
                continue
            visited.add(node)
            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
        
        return False
    
    def canReachCorner(self, X, Y, circles):
        """
        Check if there is a path from the left edge to the right edge of the rectangle,
        avoiding all circles.
        """
        self.build_graph(X, Y, circles)
        
        # Check all critical edge pairs
        critical_pairs = [
            (self.circle_count + 3, self.circle_count + 2),  # Left-Bottom
            (self.circle_count + 3, self.circle_count+1),      # Left-Right
            (self.circle_count, self.circle_count + 2),  # Top-Bottom
            (self.circle_count + 1, self.circle_count)       # Right-Top
        ]
        
        #print(self.graph)
        
        for start, end in critical_pairs:
            if self.bfs(start, end):
                #print(start, end)
                return False
        
        return True

# # Example usage
# if __name__ == "__main__":
#     solution = Solution()
    
#     # Example 1
#     X = 3
#     Y = 4
#     circles = [[2, 1, 1]]
#     print(solution.is_path_possible(X, Y, circles))  # Output: True

#     # Example 2
#     X = 3
#     Y = 3
#     circles = [[1, 1, 2]]
#     print(solution.is_path_possible(X, Y, circles))  # Output: False

#     # Example 3
#     X = 3
#     Y = 3
#     circles = [[2, 1, 1], [1, 2, 1]]
#     print(solution.is_path_possible(X, Y, circles))  # Output: False

66796