列表

详情

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

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

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

如果存在这样的路径，请你返回 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) 的路径。

 

提示：

相似题目

统计一个圆中点的数目

判断一个点是否可以到达

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: bool canReachCorner(int X, int Y, vector<vector<int>>& circles) { } };

javascript 解法, 执行用时: 44 ms, 内存消耗: 59 MB, 提交时间: 2024-11-08 09:18:56 

/**
 * @param {number} X
 * @param {number} Y
 * @param {number[][]} circles
 * @return {boolean}
 */
var canReachCorner = function(X, Y, circles) {
    // 判断点 (x, y) 是否在圆 (ox, oy, r) 内
    function inCircle(ox, oy, r, x, y) {
        return BigInt(ox - x) * BigInt(ox - x) +
               BigInt(oy - y) * BigInt(oy - y) <= BigInt(r) * BigInt(r);
    }

    const BX = BigInt(X), BY = BigInt(Y);
    const vis = new Array(circles.length).fill(false);
    function dfs(i) {
        let [x1, y1, r1] = circles[i];
        // 圆 i 是否与矩形右边界/下边界相交相切
        if (y1 <= Y && Math.abs(x1 - X) <= r1 ||
            x1 <= X && y1 <= r1 ||
            x1 > X && inCircle(x1, y1, r1, X, 0)) {
            return true;
        }
        x1 = BigInt(x1);
        y1 = BigInt(y1);
        r1 = BigInt(r1);
        vis[i] = true;
        for (let j = 0; j < circles.length; j++) {
            if (!vis[j]) {
                let [x2, y2, r2] = circles[j];
                x2 = BigInt(x2);
                y2 = BigInt(y2);
                r2 = BigInt(r2);
                // 在两圆相交相切的前提下，点 A 是否严格在矩形内
                if ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= (r1 + r2) * (r1 + r2) &&
                    x1 * r2 + x2 * r1 < (r1 + r2) * BX &&
                    y1 * r2 + y2 * r1 < (r1 + r2) * BY &&
                    dfs(j)) {
                    return true;
                }
            }
        }
        return false;
    }

    for (let i = 0; i < circles.length; i++) {
        const [x, y, r] = circles[i];
        if (inCircle(x, y, r, 0, 0) || // 圆 i 包含矩形左下角
            inCircle(x, y, r, X, Y) || // 圆 i 包含矩形右上角
            // 圆 i 是否与矩形上边界/左边界相交相切
            !vis[i] && (x <= X && Math.abs(y - Y) <= r ||
                        y <= Y && x <= r ||
                        y > Y && inCircle(x, y, r, 0, Y)) && dfs(i)) {
            return false;
        }
    }
    return true;
};

rust 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2024-11-08 09:18:42 

impl Solution {
    pub fn can_reach_corner(x_corner: i32, y_corner: i32, circles: Vec<Vec<i32>>) -> bool {
        let X = x_corner as i64;
        let Y = y_corner as i64;
        let mut vis = vec![false; circles.len()];
        for i in 0..circles.len() {
            let x = circles[i][0] as i64;
            let y = circles[i][1] as i64;
            let r = circles[i][2] as i64;
            if Self::in_circle(x, y, r, 0, 0) || // 圆 i 包含矩形左下角
               Self::in_circle(x, y, r, X, Y) || // 圆 i 包含矩形右上角
               // 圆 i 是否与矩形上边界/左边界相交相切
               !vis[i] && (x <= X && (y - Y).abs() <= r ||
                           y <= Y && x <= r ||
                           y > Y && Self::in_circle(x, y, r, 0, Y)) && Self::dfs(i, X, Y, &circles, &mut vis) {
                return false;
            }
        }
        true
    }

    // 判断点 (x,y) 是否在圆 (ox,oy,r) 内
    fn in_circle(ox: i64, oy: i64, r: i64, x: i64, y: i64) -> bool {
        (ox - x) * (ox - x) + (oy - y) * (oy - y) <= r * r
    }

    fn dfs(i: usize, x: i64, y: i64, circles: &Vec<Vec<i32>>, vis: &mut Vec<bool>) -> bool {
        let x1 = circles[i][0] as i64;
        let y1 = circles[i][1] as i64;
        let r1 = circles[i][2] as i64;
        // 圆 i 是否与矩形右边界/下边界相交相切
        if y1 <= y && (x1 - x).abs() <= r1 ||
           x1 <= x && y1 <= r1 ||
           x1 > x && Self::in_circle(x1, y1, r1, x, 0) {
            return true;
        }
        vis[i] = true;
        for (j, c2) in circles.iter().enumerate() {
            let x2 = c2[0] as i64;
            let y2 = c2[1] as i64;
            let r2 = c2[2] as i64;
            // 在两圆相交相切的前提下，点 A 是否严格在矩形内
            if !vis[j] && (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= (r1 + r2) * (r1 + r2) &&
               x1 * r2 + x2 * r1 < (r1 + r2) * x &&
               y1 * r2 + y2 * r1 < (r1 + r2) * y &&
               Self::dfs(j, x, y, circles, vis) {
                return true;
            }
        }
        false
    }
}

golang 解法, 执行用时: 71 ms, 内存消耗: 6.5 MB, 提交时间: 2024-07-29 17:52:06 

func canReachCorner(x, y int, a [][]int) bool {
	n := len(a)
	// 并查集中的 n 表示左边界或上边界，n+1 表示下边界或右边界
	fa := make([]int, n+2)
	for i := range fa {
		fa[i] = i
	}
	// 非递归并查集
	find := func(x int) int {
		rt := x
		for fa[rt] != rt {
			rt = fa[rt]
		}
		for fa[x] != rt {
			fa[x], x = rt, fa[x]
		}
		return rt
	}
	merge := func(x, y int) {
		fa[find(x)] = find(y)
	}
	for i, c := range a {
		ox, oy, r := c[0], c[1], c[2]
		if ox <= r || oy+r >= y { // 圆 i 和左边界或上边界有交集
			merge(i, n)
		}
		if oy <= r || ox+r >= x { // 圆 i 和下边界或右边界有交集
			merge(i, n+1)
		}
		for j, q := range a[:i] {
			if (ox-q[0])*(ox-q[0])+(oy-q[1])*(oy-q[1]) <= (r+q[2])*(r+q[2]) {
				merge(i, j) // 圆 i 和圆 j 有交集
			}
		}
		if find(n) == find(n+1) { // 无法到达终点
			return false
		}
	}
	return true
}

java 解法, 执行用时: 47 ms, 内存消耗: 43.8 MB, 提交时间: 2024-07-29 17:51:45 

class UnionFind {
    private final int[] fa;

    public UnionFind(int size) {
        fa = new int[size];
        for (int i = 1; i < size; i++) {
            fa[i] = i;
        }
    }

    public int find(int x) {
        if (fa[x] != x) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    public void merge(int x, int y) {
        fa[find(x)] = find(y);
    }
}

class Solution {
    public boolean canReachCorner(int x, int y, int[][] circles) {
        int n = circles.length;
        // 并查集中的 n 表示左边界或上边界，n+1 表示下边界或右边界
        UnionFind uf = new UnionFind(n + 2);
        for (int i = 0; i < n; i++) {
            int[] c = circles[i];
            int ox = c[0], oy = c[1], r = c[2];
            if (ox <= r || oy + r >= y) { // 圆 i 和左边界或上边界有交集
                uf.merge(i, n);
            }
            if (oy <= r || ox + r >= x) { // 圆 i 和下边界或右边界有交集
                uf.merge(i, n + 1);
            }
            for (int j = 0; j < i; j++) {
                int[] q = circles[j];
                if ((long) (ox - q[0]) * (ox - q[0]) + (long) (oy - q[1]) * (oy - q[1]) <= (long) (r + q[2]) * (r + q[2])) {
                    uf.merge(i, j); // 圆 i 和圆 j 有交集
                }
            }
            if (uf.find(n) == uf.find(n + 1)) { // 无法到达终点
                return false;
            }
        }
        return true;
    }
}

cpp 解法, 执行用时: 122 ms, 内存消耗: 38.9 MB, 提交时间: 2024-07-29 17:51:31 

class Solution {
public:
    bool canReachCorner(int x, int y, vector<vector<int>>& a) {
        int n = a.size();
        // 并查集中的 n 表示左边界或上边界，n+1 表示下边界或右边界
        vector<int> fa(n + 2);
        iota(fa.begin(), fa.end(), 0);
        // 非递归并查集
        auto find = [&](int x) {
            int rt = x;
            while (fa[rt] != rt) {
                rt = fa[rt];
            }
            while (fa[x] != rt) {
                int temp = fa[x];
                fa[x] = rt;
                x = temp;
            }
            return rt;
        };
        auto merge = [&](int x, int y) {
            fa[find(x)] = find(y);
        };

        for (int i = 0; i < a.size(); i++) {
            int ox = a[i][0], oy = a[i][1], r = a[i][2];
            if (ox <= r || oy + r >= y) { // 圆 i 和左边界或上边界有交集
                merge(i, n);
            }
            if (oy <= r || ox + r >= x) { // 圆 i 和下边界或右边界有交集
                merge(i, n + 1);
            }
            for (int j = 0; j < i; j++) {
                int qx = a[j][0], qy = a[j][1], qr = a[j][2];
                if ((long long) (ox - qx) * (ox - qx) + (long long) (oy - qy) * (oy - qy) <= (long long) (r + qr) * (r + qr)) {
                    merge(i, j); // 圆 i 和圆 j 有交集
                }
            }
            if (find(n) == find(n + 1)) { // 无法到达终点
                return false;
            }
        }
        return true;
    }
};

python3 解法, 执行用时: 1818 ms, 内存消耗: 17.1 MB, 提交时间: 2024-07-29 17:51:17 

class Solution:
    def canReachCorner(self, x: int, y: int, a: List[List[int]]) -> bool:
        n = len(a)
        # 并查集中的 n 表示左边界或上边界，n+1 表示下边界或右边界
        fa = list(range(n + 2))
        # 非递归并查集
        def find(x: int) -> int:
            rt = x
            while fa[rt] != rt:
                rt = fa[rt]
            while fa[x] != rt:
                fa[x], x = rt, fa[x]
            return rt
        def merge(x: int, y: int) -> None:
            fa[find(x)] = find(y)

        for i, (ox, oy, r) in enumerate(a):
            if ox <= r or oy + r >= y:  # 圆 i 和左边界或上边界有交集
                merge(i, n)
            if oy <= r or ox + r >= x:  # 圆 i 和下边界或右边界有交集
                merge(i, n + 1)
            for j, (qx, qy, qr) in enumerate(a[:i]):
                if (ox - qx) * (ox - qx) + (oy - qy) * (oy - qy) <= (r + qr) * (r + qr):
                    merge(i, j)  # 圆 i 和圆 j 有交集
            if find(n) == find(n + 1):  # 无法到达终点
                return False
        return True

上一题

© 2024 leetcode.cn