【Leetcode 每日一题 - 补卡】3235. 判断矩形的两个角落是否可达
问题背景
给你两个正整数
x
C
o
r
n
e
r
xCorner
xCorner 和
y
C
o
r
n
e
r
yCorner
yCorner 和一个二维整数数组
c
i
r
c
l
e
s
circles
circles，其中
c
i
r
c
l
e
s
[
i
]
=
[
x
i
,
y
i
,
r
i
]
circles[i] = [x_i, y_i, r_i]
circles[i]=[xi,yi,ri] 表示一个圆心在
(
x
i
,
y
i
)
(x_i, y_i)
(xi,yi) 半径为
r
i
r_i
ri 的圆。
坐标平面内有一个左下角在原点，右上角在
(
x
C
o
r
n
e
r
,
y
C
o
r
n
e
r
)
(xCorner, yCorner)
(xCorner,yCorner) 的矩形。你需要判断是否存在一条从左下角到右上角的路径满足：路径 完全 在矩形内部，不会 触碰或者经过 任何 圆的内部和边界，同时 只 在起点和终点接触到矩形。
如果存在这样的路径，请你返回
t
r
u
e
true
true，否则返回
f
a
l
s
e
false
false。
数据约束
- 3 ≤ x C o r n e r , y C o r n e r ≤ 1 0 9 3 \le xCorner, yCorner \le 10 ^ 9 3≤xCorner,yCorner≤109
- 1 ≤ c i r c l e s . l e n g t h ≤ 1000 1 \le circles.length \le 1000 1≤circles.length≤1000
- c i r c l e s [ i ] . l e n g t h = 3 circles[i].length = 3 circles[i].length=3
- 1 ≤ x i , y i , r i ≤ 1 0 9 1 \le x_i, y_i, r_i \le 10 ^ 9 1≤xi,yi,ri≤109
解题过程
超高分的周赛第四题，看了几个题解也没有完全懂，硬着头皮尝试理解一下。
把圆看作矩形上的障碍，要判断是否从左下角到右上角可达，可以反过来判断作为障碍的圆是不是没有把可能的路径全部堵死。
换句话说，本题中可以选择圆作为遍历判断的对象。
那考虑单个圆的情况，以下情形会导致路径被切断（假设圆心横坐标为
x
x
x，纵坐标为
y
y
y）：
- 矩形的左下角 ( 0 , 0 ) (0, 0) (0,0) 在某个圆内部，根本就没有可能的出发路径。
- 矩形的右上角 ( x C o r n e r , y C o r n e r ) (xCorner, yCorner) (xCorner,yCorner) 在某个圆内部，根本就没有可能的到达路径。
多个圆的情况，可以转化为考虑多次两个圆的情形，用
D
F
S
DFS
DFS 来辅助确定所有多圆的情形。要保证两个圆能够把路径切断，必须其中一个圆与矩阵的左或上边界相切或相交，另一个圆与矩阵的右或下边界相切或相交，并且这两个圆本身也需要相切或相交。
但是单单满足这个条件是不够的，如果两个圆跨边的话，也可能不会覆盖路径（参考 灵神的分析 ）。因此，额外引入两个圆交集上任意一点与矩形的关系，来确定两个圆是否能截断矩形。如果这一点在矩形内部，那么满足上述条件的圆能够有效截断矩形，在遍历的时候应认为它们相互可达，也就是题解中所说的连边。
选取两圆连线上按半径比例分割的点作为用来判断交集是否在矩形内部的点，这个点就是两圆相切的极限情况下的切点。
假设两个圆的横纵坐标与半径，分别用
x
1
,
y
1
,
r
1
x_1,y_1,r_1
x1,y1,r1 与
x
2
,
y
2
,
r
2
x_2,y_2,r_2
x2,y2,r2 来表示。那么上述点的横坐标为
x
1
+
r
1
r
1
+
r
2
∗
(
x
2
−
x
1
)
=
x
1
r
2
+
x
2
r
1
r
1
+
r
2
x_1 + \frac {r_1} {r_1 + r_ 2} * (x_2 - x_1) = \frac {x_1 r_2 + x_2 r_1} {r_1 + r_2}
x1+r1+r2r1∗(x2−x1)=r1+r2x1r2+x2r1，同理，纵坐标为
y
1
r
2
+
y
2
r
1
r
1
+
r
2
\frac {y_1 r_2 + y_2 r_1} {r_1 + r_2}
r1+r2y1r2+y2r1。
这个点在矩形内的条件：
{
x
1
r
2
+
x
2
r
1
r
1
+
r
2
<
x
C
o
r
n
e
r
y
1
r
2
+
y
2
r
1
r
1
+
r
2
<
y
C
o
r
n
e
r
\ \begin{cases} \frac {x_1 r_2 + x_2 r_1} {r_1 + r_2} \lt xCorner \\ \frac {y_1 r_2 + y_2 r_1} {r_1 + r_2} \lt yCorner \\ \end{cases}
{r1+r2x1r2+x2r1<xCornerr1+r2y1r2+y2r1<yCorner，即
{
x
1
r
2
+
x
2
r
1
<
(
r
1
+
r
2
)
∗
x
C
o
r
n
e
r
y
1
r
2
+
y
2
r
1
<
(
r
1
+
r
2
)
∗
y
C
o
r
n
e
r
\ \begin{cases} x_1 r_2 + x_2 r_1 \lt (r_1 + r_2) * xCorner \\ y_1 r_2 + y_2 r_1 \lt (r_1 + r_2) * yCorner \\ \end{cases}
{x1r2+x2r1<(r1+r2)∗xCornery1r2+y2r1<(r1+r2)∗yCorner
最终将这种可能描述为：圆与矩形的左边界或者下边界相切或相交，并且能够找到一个与矩形右边界或者下边界相切或相交的可达的圆。
这题最终困难的地方在于，用图论的知识严格证明上述就是所有可能的没有路径的情况。这要求比较扎实的数学知识，完全在我的能力范围之外了，目前打算先好这里遍历的部分。
具体实现
class Solution {
public boolean canReachCorner(int xCorner, int yCorner, int[][] circles) {
int n = circles.length;
boolean[] vis = new boolean[n];
for(int i = 0; i < n; i++) {
long x = circles[i][0], y = circles[i][1], r = circles[i][2];
if(inCircle(x, y, r, 0, 0) || // 矩形左下角在某个圆内部
inCircle(x, y, r, xCorner, yCorner) || // 矩形右上角在某个圆内部
// 一个未访问过的圆满足矩形的左或上边界条件，遍历找到满足条件的另一个圆
!vis[i] && (x <= xCorner && Math.abs(y - yCorner) <= r || y <= yCorner && x <= r) && dfs(i, xCorner, yCorner, circles, vis)) {
return false;
}
}
return true;
}
// 判断某点是否在圆内部
private boolean inCircle(long oX, long oY, long r, long x, long y) {
return (oX - x) * (oX - x) + (oY - y) * (oY - y) <= r * r;
}
// 遍历并判断是否能找到与矩形右或下边界相切或相交的可达的圆
private boolean dfs(int i, int xCorner, int yCorner, int[][] circles, boolean[] vis) {
long x1 = circles[i][0], y1 = circles[i][1], r1 = circles[i][2];
// 找到可达的圆，判断发现它满足矩形的右或下边界条件
if(y1 <= yCorner && Math.abs(x1 - xCorner) <= r1 || x1 <= xCorner && y1 <= r1) {
return true;
}
vis[i] = true; // 标记这个圆被访问过
for(int j = 0; j < circles.length; j++) {
long x2 = circles[j][0], y2 = circles[j][1], r2 = circles[j][2];
if(!vis[j] && // 圆未被访问过
// 两圆心之间的距离不大于半径之和，两圆相切或相交
(x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= (r1 + r2) * (r1 + r2) &&
// 推导出来的条件，保证圆的交集有一部分在矩形内部
x1 * r2 + x2 * r1 < (r1 + r2) * xCorner &&
y1 * r2 + y2 * r1 < (r1 + r2) * yCorner &&
dfs(j, xCorner, yCorner, circles, vis)) {
return true;
}
}
return false;
}
}