How can I check if a path exists between the bottom-left and top-right corners?

You can model the problem as a graph and use algorithms like BFS or DFS to explore if there's a valid path that avoids all circles.

What geometric calculations are required to avoid circles in the path?

You need to calculate the Euclidean distance between points on the path and circle centers to ensure no intersection occurs.

What is the time complexity of the solution?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges in the graph representation.

Can this problem be solved using the Union-Find algorithm?

Yes, Union-Find can be used to efficiently determine whether the two corners are connected by a valid path avoiding obstacles.

How do I handle edge cases with circle intersections?

Ensure that before exploring a potential path, you check if it intersects any circle by comparing distances to circle centers.

#3235

Hard

auto_awesome数组·数学

LeetCode 题解工作台

判断矩形的两个角落是否可达

给你两个正整数 xCorner 和 yCorner 和一个二维整数数组 circles ，其中 circles[i] = [x i , y i , r i ] 表示一个圆心在 (x i , y i ) 半径为 r i 的圆。坐标平面内有一个左下角在原点，右上角在 (xCorner, yCorner…

数组数学深度优先搜索广度优先搜索并查集

题目描述

给你两个正整数 xCorner 和 yCorner 和一个二维整数数组 circles ，其中 circles[i] = [x_i, y_i, r_i] 表示一个圆心在 (x_i, y_i) 半径为 r_i 的圆。

坐标平面内有一个左下角在原点，右上角在 (xCorner, yCorner) 的矩形。你需要判断是否存在一条从左下角到右上角的路径满足：路径完全在矩形内部，不会触碰或者经过任何圆的内部和边界，同时只在起点和终点接触到矩形。

如果存在这样的路径，请你返回 true ，否则返回 false 。

示例 1：

输入：X = 3, Y = 4, circles = [[2,1,1]]

输出：true

解释：

黑色曲线表示一条从 (0, 0) 到 (3, 4) 的路径。

示例 2：

输入：X = 3, Y = 3, circles = [[1,1,2]]

输出：false

解释：

不存在从 (0, 0) 到 (3, 3) 的路径。

示例 3：

输入：X = 3, Y = 3, circles = [[2,1,1],[1,2,1]]

输出：false

解释：

不存在从 (0, 0) 到 (3, 3) 的路径。

示例 4：

输入：X = 4, Y = 4, circles = [[5,5,1]]

输出：true

解释：

提示：

3 <= xCorner, yCorner <= 10⁹
1 <= circles.length <= 1000
circles[i].length == 3
1 <= x_i, y_i, r_i <= 10⁹

lightbulb

解题思路

方法一：DFS + 数学

根据题意，我们分情况讨论：

当 circles 中只有一个圆时：

如果起点 $(0, 0)$ 在圆内（包括边界），或者终点 $(\textit{xCorner}, \textit{yCorner})$ 在圆内，那么无法满足“不触碰圆”的条件；
如果圆与矩形的左侧或上侧有交点，且与矩形的右侧或下侧有交点，这种情况下，圆会阻断从矩形左下角到右上角的路径，也无法满足“不触碰圆”的条件。

当 circles 中有多个圆时：

与上述情况类似，如果起点或终点在圆内时，无法满足“不触碰圆”的条件。
如果有多个圆，多个圆之间可能在矩形内相交，合并形成更大的障碍区域。只要这个障碍区域与矩形的左侧或上侧有交点，且与矩形的右侧或下侧有交点，那么无法满足“不触碰圆”的条件。如果相交区域不在矩形内部，不能进行合并，因为相交的区域无法阻断矩形内部路径。另外，如果相交的区域有一部分在矩形内，有一部分在矩形外，这些圆都可以作为搜索的起点或终点，可以合并，也可以不合并。我们只要任选相交的其中一个点，如果这个点在矩形内，我们就可以将这些圆合并。

根据上述分析，我们遍历所有圆，对于当前遍历到的圆，如果起点或终点在圆内，我们直接返回 false。否则，如果这个点没有被访问过，且这个圆与矩形的左侧或上侧有交点，我们就从这个圆开始进行深度优先搜索，搜索过程中，如果找到了一个圆，它与矩形的右侧或下侧有交点，说明圆形成的障碍区域阻断了从矩形左下角到右上角的路径，我们就返回 false。

我们定义 $\textit{dfs}(i)$ 表示从第 $i$ 个圆开始进行深度优先搜索，如果找到了一个圆，它与矩形的右侧或下侧有交点，返回 true，否则返回 false。

函数 $\textit{dfs}(i)$ 的执行过程如下：

如果当前圆与矩形的右侧或下侧有交点，返回 true；
否则，我们将当前圆标记为已访问；
接下来，遍历其它所有圆，如果圆 $j$ 没被访问过，且圆 $i$ 和圆 $j$ 相交，且这两个圆的其中一个交点在矩形内，我们就继续从圆 $j$ 开始进行深度优先搜索，如果找到了一个圆，它与矩形的右侧或下侧有交点，返回 true；
如果没有找到这样的圆，返回 false。

上面的过程中，我们需要在圆 $O_1 = (x_1, y_1, r_1)$ 和 $O_2 = (x_2, y_2, r_2)$ 之间判断是否相交，如果两个圆相交，那么它们的圆心之间的距离不超过两个圆的半径之和，即 $(x_1 - x_2)^2 + (y_1 - y_2)^2 \le (r_1 + r_2)^2$ 。

我们还需要寻找两个圆的一个交点，我们取一个点 $A = (x, y)$ ，满足 $\frac{O_1 A}{O_1 O_2} = \frac{r_1}{r_1 + r_2}$ ，如果两圆相交，那么点 $A$ 一定在交集中，此时 $\frac{x - x_1}{x_2 - x_1} = \frac{r_1}{r_1 + r_2}$ ，解得 $x = \frac{x_1 r_2 + x_2 r_1}{r_1 + r_2}$ ，同理，有 $y = \frac{y_1 r_2 + y_2 r_1}{r_1 + r_2}$ 。只要这个点在矩形内，我们就可以继续进行深度优先搜索，即满足：

\begin{cases} x_1 r_2 + x_2 r_1 < (r_1 + r_2) \times \textit{xCorner} \\ y_1 r_2 + y_2 r_1 < (r_1 + r_2) \times \textit{yCorner} \end{cases}

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为圆的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

class Solution:
    def canReachCorner(
        self, xCorner: int, yCorner: int, circles: List[List[int]]
    ) -> bool:
        def in_circle(x: int, y: int, cx: int, cy: int, r: int) -> int:
            return (x - cx) ** 2 + (y - cy) ** 2 <= r**2

        def cross_left_top(cx: int, cy: int, r: int) -> bool:
            a = abs(cx) <= r and 0 <= cy <= yCorner
            b = abs(cy - yCorner) <= r and 0 <= cx <= xCorner
            return a or b

        def cross_right_bottom(cx: int, cy: int, r: int) -> bool:
            a = abs(cx - xCorner) <= r and 0 <= cy <= yCorner
            b = abs(cy) <= r and 0 <= cx <= xCorner
            return a or b

        def dfs(i: int) -> bool:
            x1, y1, r1 = circles[i]
            if cross_right_bottom(x1, y1, r1):
                return True
            vis[i] = True
            for j, (x2, y2, r2) in enumerate(circles):
                if vis[j] or not ((x1 - x2) ** 2 + (y1 - y2) ** 2 <= (r1 + r2) ** 2):
                    continue
                if (
                    (x1 * r2 + x2 * r1 < (r1 + r2) * xCorner)
                    and (y1 * r2 + y2 * r1 < (r1 + r2) * yCorner)
                    and dfs(j)
                ):
                    return True
            return False

        vis = [False] * len(circles)
        for i, (x, y, r) in enumerate(circles):
            if in_circle(0, 0, x, y, r) or in_circle(xCorner, yCorner, x, y, r):
                return False
            if (not vis[i]) and cross_left_top(x, y, r) and dfs(i):
                return False
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for an understanding of graph theory applied to geometry.
question_mark
Assess the candidate's ability to efficiently handle obstacles (circles) in pathfinding.
question_mark
Evaluate how well the candidate combines algorithmic approaches like DFS/BFS with mathematical geometry.

warning

常见陷阱

外企场景

error
Ignoring edge cases like when the two corners are inside a circle or when circles touch the rectangle boundaries.
error
Not properly handling circle intersection checks and assuming direct paths without verifying geometry.
error
Overcomplicating the problem with unnecessary computations instead of leveraging efficient graph traversal algorithms.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the rectangle's top-right corner changes dynamically during the pathfinding process?
arrow_right_alt
How does the solution change when the number of circles is significantly larger (e.g., 1000+)?
arrow_right_alt
How would the approach change if there were multiple rectangles or obstacles to consider simultaneously?

help

常见问题

外企场景

继续练习

#2101 引爆最多的炸弹 #3493 属性图 #3607 电网维护