一个有趣的算法题：别惊动魔王？
题目如下：
琼斯博士在寻宝的过程中，来到了一个平面图呈矩形的封闭房间。
矩形的宽度为w，高度为h。为方便描述，我们将矩形左上角坐标定为(0, 0)，右下角坐标定为(w, h)。
房间的入口在矩形上沿的中点(即(w/2, 0))，出口在矩形下沿的中点(即(w/2, h))。狡猾的魔王还放置了许多红外探测器，一旦进入探测器的探测半径以内，将触发警报。
现在琼斯博士向您求助，他能否全身而退不惊动魔王？
输入：boolean escape(int w, int h, int n, double[] x, double[] y, double[] r)
w为矩形宽度，h为矩形高度，n为探测器总数。第i个探测器的坐标为(x[i],y[i])，探测半径为r[i]。
输出：true or false
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
不求最短，只求能走的话，把探测器的边缘当作墙，左手扶墙走，如果走回入口说明是封闭的无法脱出，如果走到出口那就可以走出去
先求所有的直线／圆之间的交点，分别记录下来（四个顶点和入口出口也都记录为交点），然后从入口向左的直线开始找最近的交点，碰到交点就把“当前在走的线”更换，然后循环继续找交点，直到找到入口“交点”返回false，出口“交点”返回true
“最近的交点”的搜索方向，如果当前在走的线是直线（边），那么就是朝内部（上边沿的下面，etc），如果是圆弧，那么就是朝远离圆心的方向
求搜索方向，确定方向后找下一个节点等操作都是o1的，求所有交点虽然是平方级，但是是探测器数量的平方，感觉上应该还比较快
想到一个简化问题的办法不知道是不是有用...
任意两个探测器之间距离大于半径和那么就可以通过, 小于就不能, 那么我们可以把不能通过的两个探测器之间连上线, 如果探测器覆盖范围到了墙壁, 那么这个点和墙壁之间也连上线, 后面就只需要判断这些线和墙壁有没有把出口和入口分开了.
嗯, 然后想到了这个办法:
后面的想法有点暴力, 那就是把所有的线段交点, 包括和墙壁连线的端点都找出来, 这里不用管几何的问题, 只要管节点相连的问题, 这样这个问题就化简成一个图论的问题了.
1. 从起点开始往外走, 每一步看下一个节点和几个节点相连
2. 如果只和本节点和另一个节点相连, 走到这个节点.
3. 如果下一个节点和两个以上的节点相连, 那么将这个节点分成两个, 其中一个和其他节点继续相连, 另一个只和这个节点和其他相连的点中的一个相连, 走到这个节点.
用这样的办法就可以把空间完全拆分成两部分, 这样的循环结束条件是走到终点或者走回起点, 分别对应true/false
起点的左边，也就是(0, 0)到(w/2, 0)，标记为0，(w/2, 0)到(w, 0)为1，(w, 0)到(w, h)为2，依次下来把矩形的四条边分为了6部分。要想答案为true，0和1必定不能联通，0和2也不能联通，把这些不能联通的条件罗列出来。给每个探测器标记，6,7,8,。。。如果任意两个探测器能互相覆盖（也就是圆心距离小于半径之和），就在他们之间连一条无向边。还要判断这些探测器和0到5这6个矩形的边能否互相覆盖，如果能的话也连一条无向边。这样就建立了一个无向图。根据题意，判断0和1两个点之间是否联通，0和2两个点之间是否联通，等等，这样就转化为了一个无向图中一个结点与另一个节点是否可达的图论问题了。最终确定是true或者false。
题目没有说入口和出口在哪里
如果入口和出口是对角线的话
只需要判断对边上的探测器有没有重合&&出入口夹角边上的探测器有没有重合&&有没有探测器覆盖对边，有的话就false，没有就true
如果是邻角就没啥好说的了吧，只要看这边上有没有探测器能探测到就好了
如果出入口不在角上
将长方形按照出入口XY裁减为四个长方形，然后用上面的方法挨个组合，有一个true就妥了
感觉可以用到在算法 4 书里的 Connectivity 连接性类型题目的做法。其实这里就是在一个二维数组上的数据上，把探测器覆盖区域都标上，然后看没有标记上的，是否能从入口到出口连一条路出来
因为走空地是无意义的，将起点终点和四个角，以及所有圆圆交点和圆线交点求出，再判定每段由两点确定的圆弧和直线是否有效（看中点是否有被任何一个圆覆盖或不在矩形内），所有有效圆弧或直线的两个端点视为连通，然后bfs还是dfs还是并查集啥的怎么样都好了。
只是想知道能不能走出去的话，有个法子很简单，从出口点开始染色，每次把邻近点中排除探测器范围内的点染色，然后把这些点的邻近点列为下一轮染色的区域，直到入口点被染色即为可以逃离，或者无邻近点可被染色了而入口点未被染色则为不可逃离。
BFS掃描一次就好了. 看能不能找到從A到B的path, 把其中警報的地方mark為不可經過.