力扣每日一题 3235. 判断矩形的两个角落是否可达

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

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

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

今天的困难题是真的困难，以前的虽然也难，但至少我知道我是能写出来的，而今天的题目，一看就知道是个数学几何，而且看数据范围就知道还得套其他方法，只能说完全没有思路。

没办法，只能看题解了。看完题解之后发现，这居然是套了个基础的图论。如果不考虑图形相交的写法的话，这个题目要是能把想到把圆和边抽象出来的话，这题目也没那么难。

方法是这样的，把整个n个圆和矩形的4条边都抽象成图里的点，如果他们有相交，就把图里的点进行连线，那么要判断矩形的两个角落是否可达就可以简单的变成判断图里的四条矩形边任意两条是否联通，如果联通了，那么说明存在一些圆横跨了矩形的左右或者上下或者堵住了一个角落，也就是说不可达，否则就意味这可达。

贴个官方的题解和灵神的题解

class Solution {
    // 判断点 (x,y) 是否在圆 (ox,oy,r) 内
    bool in_circle(long long ox, long long oy, long long r, long long x, long long y) {
        return (ox - x) * (ox - x) + (oy - y) * (oy - y) <= r * r;
    }

public:
    bool canReachCorner(int X, int Y, vector<vector<int>>& circles) {
        int n = circles.size();
        vector<int> vis(n);
        auto dfs = [&](auto&& dfs, int i) -> bool {
            long long x1 = circles[i][0], y1 = circles[i][1], r1 = circles[i][2];
            // 圆 i 是否与矩形右边界/下边界相交相切
            if (y1 <= Y && abs(x1 - X) <= r1 ||
                x1 <= X && y1 <= r1 ||
                x1 > X && in_circle(x1, y1, r1, X, 0)) {
                return true;
            }
            vis[i] = true;
            for (int j = 0; j < n; j++) {
                long long x2 = circles[j][0], y2 = circles[j][1], r2 = circles[j][2];
                // 在两圆相交相切的前提下，点 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 &&
                    dfs(dfs, j)) {
                    return true;
                }
            }
            return false;
        };
        for (int i = 0; i < n; i++) {
            long long x = circles[i][0], y = circles[i][1], r = circles[i][2];
            if (in_circle(x, y, r, 0, 0) || // 圆 i 包含矩形左下角
                in_circle(x, y, r, X, Y) || // 圆 i 包含矩形右上角
                // 圆 i 是否与矩形上边界/左边界相交相切
                !vis[i] && (x <= X && abs(y - Y) <= r ||
                            y <= Y && x <= r ||
                            y > Y && in_circle(x, y, r, 0, Y)) && dfs(dfs, i)) {
                return false;
            }
        }
        return true;
    }
};

代码其实也没那么长，很大部分还是在于对几何相交的处理。

时间复杂度O(n*n)，空间复杂度O(n).

原文地址：https://blog.csdn.net/qq_41529799/article/details/143637120

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！