Kimi K2.6 快速思考 LeetCode 3235. 判断矩形的两个角落是否可达 Java实现
<|tool_calls_section_begin|> <|tool_call_begin|> articleweb_search:11#3web_search:11#2
LeetCode 3235. 判断矩形的两个角落是否可达 - Java 实现
题目概述
判断是否存在一条从矩形左下角 `(0, 0)` 到右上角 `(xCorner, yCorner)` 的路径，路径完全在矩形内部，不触碰任何圆的内部和边界，只在起点和终点接触矩形边界。
核心思路
这道题的关键在于逆向思考：不是找可达路径，而是判断圆是否形成了阻断路径的屏障。
如果一系列相交的圆从左边界/上边界连通到右边界/下边界，或者连通左边界到下边界、上边界到右边界，则会阻断从左下角到右上角的路径。
解法一：DFS + 几何判断（推荐）
```java
class Solution {
private int[][] circles;
private int xCorner, yCorner;
private boolean[] vis;
public boolean canReachCorner(int xCorner, int yCorner, int[][] circles) {
int n = circles.length;
this.circles = circles;
this.xCorner = xCorner;
this.yCorner = yCorner;
vis = new boolean[n];
for (int i = 0; i < n; ++i) {
var c = circles[i];
int 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;
}
// 判断点 (x,y) 是否在圆 (cx,cy,r) 内（含边界）
private boolean inCircle(long x, long y, long cx, long cy, long r) {
return (x - cx) * (x - cx) + (y - cy) * (y - cy) <= r * r;
}
// 判断圆是否与矩形的左边界或上边界相交
private boolean crossLeftTop(long cx, long cy, long r) {
boolean a = Math.abs(cx) <= r && (cy >= 0 && cy <= yCorner);
boolean b = Math.abs(cy - yCorner) <= r && (cx >= 0 && cx <= xCorner);
return a || b;
}
// 判断圆是否与矩形的右边界或下边界相交
private boolean crossRightBottom(long cx, long cy, long r) {
boolean a = Math.abs(cx - xCorner) <= r && (cy >= 0 && cy <= yCorner);
boolean b = Math.abs(cy) <= r && (cx >= 0 && cx <= xCorner);
return a || b;
}
// DFS：从当前圆出发，寻找是否能连通到右下边界
private boolean dfs(int i) {
var c = circles[i];
long x1 = c[0], y1 = c[1], r1 = c[2];
// 当前圆已与右下边界相交，说明形成阻断
if (crossRightBottom(x1, y1, r1)) {
return true;
}
vis[i] = true;
for (int j = 0; j < circles.length; ++j) {
var c2 = circles[j];
long x2 = c2[0], y2 = c2[1], r2 = c2[2];
if (vis[j]) continue;
// 两圆不相交
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;
}
}
```
解法二：并查集（Union-Find）
```java
class UnionFind {
private int[] id;
private int[] rank;
public UnionFind(int n) {
id = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i) id[i] = i;
}
public void unionByRank(int u, int v) {
int i = find(u), j = find(v);
if (i == j) return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
public int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
}
class Solution {
public boolean canReachCorner(int X, int Y, int[][] circles) {
int n = circles.length;
// 虚拟节点：n 代表 (0,0) 区域，n+1 代表 (X,Y) 区域
UnionFind uf = new UnionFind(n + 2);
for (int i = 0; i < n; ++i) {
int x = circles[i][0], y = circles[i][1], r = circles[i][2];
// 圆与左边界或上边界相交，连到 (0,0) 区域
if (x - r <= 0 || y + r >= Y)
uf.unionByRank(i, n);
// 圆与右边界或下边界相交，连到 (X,Y) 区域
if (x + r >= X || y - r <= 0)
uf.unionByRank(i, n + 1);
// 与其他圆相交则合并
for (int j = 0; j < i; j++) {
int x2 = circles[j][0], y2 = circles[j][1], r2 = circles[j][2];
if ((long)(x - x2) * (x - x2) + (long)(y - y2) * (y - y2)
<= (long)(r + r2) * (r + r2)) {
uf.unionByRank(i, j);
}
}
}
// 如果 (0,0) 和 (X,Y) 连通，说明路径被阻断
return uf.find(n) != uf.find(n + 1);
}
}
```
关键几何判断说明
判断条件 含义
`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` 类型：坐标和半径最大可达 10^9，计算距离平方时可能溢出 `int`
2. 两圆相交的内部判断：`x1*r2 + x2*r1 < (r1+r2)*xCorner` 确保交点位于矩形内部，避免圆在矩形外相交导致的误判
3. 起点/终点检查：如果起点 `(0,0)` 或终点 `(xCorner, yCorner)` 在任意圆内，直接返回 `false`