Hard

题目描述

给定两个正整数 xCorner 和 yCorner，以及一个二维数组 circles，其中 circles[i] = [xi, yi, ri] 表示圆心在 (xi, yi)，半径为 ri 的圆。

坐标平面上有一个矩形，其左下角在原点，右上角在坐标 (xCorner, yCorner)。你需要检查是否存在一条从左下角到右上角的路径，使得整条路径都在矩形内，不接触或穿过任何圆，并且只在两个角落接触矩形。

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

示例 1：

输入：xCorner = 3, yCorner = 4, circles = [[2,1,1]]
输出：true
解释：黑色曲线显示了 (0,0) 和 (3,4) 之间的一条可能路径。

示例 2：

输入：xCorner = 3, yCorner = 3, circles = [[1,1,2]]
输出：false
解释：不存在从 (0,0) 到 (3,3) 的路径。

示例 3：

输入：xCorner = 3, yCorner = 3, circles = [[2,1,1],[1,2,1]]
输出：false
解释：不存在从 (0,0) 到 (3,3) 的路径。

示例 4：

输入：xCorner = 4, yCorner = 4, circles = [[5,5,1]]
输出：true

约束条件：

  • 3 <= xCorner, yCorner <= 10^9
  • 1 <= circles.length <= 1000
  • circles[i].length == 3
  • 1 <= xi, yi, ri <= 10^9

解题思路

这道题的核心思想是将问题转化为图论问题，判断是否存在阻断路径的连通路径。

解题思路

  1. 问题转换：如果从(0,0)到(xCorner,yCorner)无法到达，那么必定存在一条由圆形成的"屏障"，这个屏障连接了矩形的两条相邻边。

  2. 建图策略：

    • 创建n+4个节点，前n个代表圆，后4个代表矩形的四条边（上、右、下、左）
    • 如果两个圆相交或相切，在对应节点间连边
    • 如果圆与矩形边相交或相切，在圆节点和边节点间连边

  3. 判断条件：使用并查集检查以下连通性：

    • 左边与上边连通 → 阻断从左下到右上的路径
    • 左边与右边连通 → 阻断从下到上的路径
    • 下边与上边连通 → 阻断从左到右的路径
    • 下边与右边连通 → 阻断从左下到右上的路径

  4. 几何计算：

    • 两圆相交：圆心距离 ≤ 半径之和
    • 圆与边相交：计算圆心到边的距离 ≤ 半径

如果存在任何一种阻断情况，返回false；否则返回true。

代码实现

class Solution {
public:
    bool canReachCorner(int xCorner, int yCorner, vector<vector<int>>& circles) {
        int n = circles.size();
        vector<int> parent(n + 4);
        for (int i = 0; i < n + 4; i++) parent[i] = i;
        
        function<int(int)> find = [&](int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        
        auto unite = [&](int x, int y) {
            x = find(x); y = find(y);
            if (x != y) parent[x] = y;
        };
        
        // Check if two circles intersect
        auto circlesIntersect = [&](int i, int j) {
            long long dx = (long long)circles[i][0] - circles[j][0];
            long long dy = (long long)circles[i][1] - circles[j][1];
            long long dist2 = dx * dx + dy * dy;
            long long sumR = (long long)circles[i][2] + circles[j][2];
            return dist2 <= sumR * sumR;
        };
        
        // Check if circle intersects with rectangle edges
        auto intersectsTop = [&](int i) {
            return circles[i][1] + circles[i][2] >= yCorner && 
                   circles[i][0] >= circles[i][2] && 
                   circles[i][0] <= xCorner - circles[i][2];
        };
        
        auto intersectsRight = [&](int i) {
            return circles[i][0] + circles[i][2] >= xCorner && 
                   circles[i][1] >= circles[i][2] && 
                   circles[i][1] <= yCorner - circles[i][2];
        };
        
        auto intersectsBottom = [&](int i) {
            return circles[i][1] <= circles[i][2] && 
                   circles[i][0] >= circles[i][2] && 
                   circles[i][0] <= xCorner - circles[i][2];
        };
        
        auto intersectsLeft = [&](int i) {
            return circles[i][0] <= circles[i][2] && 
                   circles[i][1] >= circles[i][2] && 
                   circles[i][1] <= yCorner - circles[i][2];
        };
        
        // Connect circles that intersect
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (circlesIntersect(i, j)) {
                    unite(i, j);
                }
            }
        }
        
        // Connect circles to edges
        for (int i = 0; i < n; i++) {
            if (intersectsTop(i)) unite(i, n);
            if (intersectsRight(i)) unite(i, n + 1);
            if (intersectsBottom(i)) unite(i, n + 2);
            if (intersectsLeft(i)) unite(i, n + 3);
        }
        
        // Check blocking conditions
        return !(find(n) == find(n + 3) || // top and left
                 find(n + 1) == find(n + 3) || // right and left
                 find(n) == find(n + 2) || // top and bottom
                 find(n + 1) == find(n + 2)); // right and bottom
    }
};

class Solution:
    def canReachCorner(self, xCorner: int, yCorner: int, circles: List[List[int]]) -> bool:
        n = len(circles)
        parent = list(range(n + 4))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[px] = py
        
        def circles_intersect(i, j):
            dx = circles[i][0] - circles[j][0]
            dy = circles[i][1] - circles[j][1]
            dist2 = dx * dx + dy * dy
            sum_r = circles[i][2] + circles[j][2]
            return dist2 <= sum_r * sum_r
        
        def intersects_top(i):
            x, y, r = circles[i]
            return y + r >= yCorner and r <= x <= xCorner - r
        
        def intersects_right(i):
            x, y, r = circles[i]
            return x + r >= xCorner and r <= y <= yCorner - r
        
        def intersects_bottom(i):
            x, y, r = circles[i]
            return y <= r and r <= x <= xCorner - r
        
        def intersects_left(i):
            x, y, r = circles[i]
            return x <= r and r <= y <= yCorner - r
        
        # Connect intersecting circles
        for i in range(n):
            for j in range(i + 1, n):
                if circles_intersect(i, j):
                    unite(i, j)
        
        # Connect circles to edges
        for i in range(n):
            if intersects_top(i):
                unite(i, n)
            if intersects_right(i):
                unite(i, n + 1)
            if intersects_bottom(i):
                unite(i, n + 2)
            if intersects_left(i):
                unite(i, n + 3)
        
        # Check blocking conditions
        return not (find(n) == find(n + 3) or  # top and left
                   find(n + 1) == find(n + 3) or  # right and left
                   find(n) == find(n + 2) or  # top and bottom
                   find(n + 1) == find(n + 2))  # right and bottom

public class Solution {
    public bool CanReachCorner(int xCorner, int yCorner, int[][] circles) {
        int n = circles.Length;
        int[] parent = new int[n + 4];
        for (int i = 0; i < n + 4; i++) parent[i] = i;
        
        int Find(int x) {
            return parent[x] == x ? x : parent[x] = Find(parent[x]);
        }
        
        void Unite(int x, int y) {
            x = Find(x); y = Find(y);
            if (x != y) parent[x] = y;
        }
        
        bool CirclesIntersect(int i, int j) {
            long dx = (long)circles[i][0] - circles[j][0];
            long dy = (long)circles[i][1] - circles[j][1];
            long dist2 = dx * dx + dy * dy;
            long sumR = (long)circles[i][2] + circles[j][2];
            return dist2 <= sumR * sumR;
        }
        
        bool IntersectsTop(int i) {
            return circles[i][1] + circles[i][2] >= yCorner && 
                   circles[i][0] >= circles[i][2] && 
                   circles[i][0] <= xCorner - circles[i][2];
        }
        
        bool IntersectsRight(int i) {
            return circles[i][0] + circles[i][2] >= xCorner && 
                   circles[i][1] >= circles[i][2] && 
                   circles[i][1] <= yCorner - circles[i][2];
        }
        
        bool IntersectsBottom(int i) {
            return circles[i][1] <= circles[i][2] && 
                   circles[i][0] >= circles[i][2] && 
                   circles[i][0] <= xCorner - circles[i][2];
        }
        
        bool IntersectsLeft(int i) {
            return circles[i][0] <= circles[i][2] && 
                   circles[i][1] >= circles[i][2] && 
                   circles[i][1] <= yCorner - circles[i][2];
        }
        
        // Connect intersecting circles
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (CirclesIntersect(i, j)) {
                    Unite(i, j);
                }
            }
        }
        
        // Connect circles to edges
        for (int i = 0; i < n; i++) {
            if (IntersectsTop(i)) Unite(i, n);
            if (IntersectsRight(i)) Unite(i, n + 1);
            if (IntersectsBottom(i)) Unite(i, n + 2);
            if (IntersectsLeft(i)) Unite(i, n + 3);
        }
        
        // Check blocking conditions
        return !(Find(n) == Find(n + 3) || 
                 Find(n + 1) == Find(n + 3) || 
                 Find(n) == Find(n + 2) || 
                 Find(n + 1) == Find(n + 2));
    }
}

var canReachCorner = function(xCorner, yCorner, circles) {
    const n = circles.length;
    const parent = Array.from({length: n + 4}, (_, i) => i);
    
    const find = (x) => {
        return parent[x]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-

相关题目