Kimi K2.6 快速 LeetCode 3235. 判断矩形的两个角落是否可达 C++实现

LeetCode 3235. 判断矩形的两个角落是否可达 — C++ 实现

题目概述

判断是否存在一条从矩形左下角 `(0, 0)` 到右上角 `(xCorner, yCorner)` 的路径，路径完全在矩形内部，不触碰任何圆的内部和边界，只在起点和终点接触矩形边界。

核心思路

逆向思考：不是找可达路径，而是判断圆是否形成了阻断路径的屏障。如果一系列相交的圆从矩形左上边界连通到右下边界，则会阻断从左下角到右上角的路径。

C++ 实现（DFS + 几何判断）

```cpp
class Solution {
public:
bool canReachCorner(int xCorner, int yCorner, vector<vector<int>>& circles) {
using ll = long long;

// 判断点 (x,y) 是否在圆 (cx,cy,r) 内（含边界）
auto inCircle = [&](ll x, ll y, ll cx, ll cy, ll r) {
return (x - cx) * (x - cx) + (y - cy) * (y - cy) <= r * r;
};

// 判断圆是否与矩形的左边界或上边界相交
auto crossLeftTop = [&](ll cx, ll cy, ll r) {
bool a = abs(cx) <= r && (cy >= 0 && cy <= yCorner);
bool b = abs(cy - yCorner) <= r && (cx >= 0 && cx <= xCorner);
return a || b;
};

// 判断圆是否与矩形的右边界或下边界相交
auto crossRightBottom = [&](ll cx, ll cy, ll r) {
bool a = abs(cx - xCorner) <= r && (cy >= 0 && cy <= yCorner);
bool b = abs(cy) <= r && (cx >= 0 && cx <= xCorner);
return a || b;
};

int n = circles.size();
vector<bool> vis(n);

// DFS：从当前圆出发，寻找是否能连通到右下边界
function<bool(int)> dfs = [&](int i) -> bool {
auto c = circles[i];
ll x1 = c[0], y1 = c[1], r1 = c[2];

// 当前圆已与右下边界相交，说明形成阻断
if (crossRightBottom(x1, y1, r1)) {
return true;
}

vis[i] = true;

for (int j = 0; j < n; ++j) {
if (vis[j]) continue;

auto c2 = circles[j];
ll x2 = c2[0], y2 = c2[1], r2 = c2[2];

// 两圆不相交
if ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) > (r1 + r2) * (r1 + r2)) {
continue;
}

// 两圆相交点在矩形内部，且能继续连通到右下边界
if (x1 * r2 + x2 * r1 < (r1 + r2) * xCorner
&& y1 * r2 + y2 * r1 < (r1 + r2) * yCorner
&& dfs(j)) {
return true;
}
}
return false;
};

for (int i = 0; i < n; ++i) {
auto c = circles[i];
ll x = c[0], y = c[1], r = c[2];

// 如果起点或终点在圆内，直接不可达
if (inCircle(0, 0, x, y, r) || inCircle(xCorner, yCorner, x, y, r)) {
return false;
}

// 如果圆与左上边界相交，且能连通到右下边界，则路径被阻断
if (!vis[i] && crossLeftTop(x, y, r) && dfs(i)) {
return false;
}
}
return true;
}
};
```

关键几何判断说明

判断条件 含义
`inCircle(px, py, cx, cy, r)` 点是否在圆内/圆上
`crossLeftTop(cx, cy, r)` 圆是否与矩形左边界或上边界相交
`crossRightBottom(cx, cy, r)` 圆是否与矩形右边界或下边界相交
`x1*r2 + x2*r1 < (r1+r2)*xCorner` 两圆交点的加权重心在矩形内部

复杂度分析

- 时间复杂度：O(n^2)，最坏情况下需要两两判断圆是否相交
- 空间复杂度：O(n)，用于访问标记数组和递归栈

注意事项

1. 使用 `long long` 类型：坐标和半径最大可达 10^9，计算距离平方时可能溢出 `int`
2. 两圆相交的内部判断：`x1*r2 + x2*r1 < (r1+r2)*xCorner` 确保交点位于矩形内部，避免圆在矩形外相交导致的误判
3. 起点/终点检查：如果起点 `(0,0)` 或终点 `(xCorner, yCorner)` 在任意圆内，直接返回 `false`