一个有趣的算法题：别惊动魔王？

Question

题目如下：
琼斯博士在寻宝的过程中，来到了一个平面图呈矩形的封闭房间。
矩形的宽度为w，高度为h。为方便描述，我们将矩形左上角坐标定为(0,0)，右下角坐标定为(w,h)。
房间的入口在矩形上沿的中点(即(w/2,0))，出口在矩形下沿的中点(即(w/2,h))。狡猾的魔王还放置了许多红外探测器，一旦进入探测器的探测半径以内，将触发警报。
现在琼斯博士向您求助，他能否全身而退不惊动魔王？
输入：booleanescape(intw,inth,intn,double[]x,double[]y,double[]r)
w为矩形宽度，h为矩形高度，n为探测器总数。第i个探测器的坐标为(x[i],y[i])，探测半径为r[i]。
输出：trueorfalse

Answer 1

想到一个简化问题的办法不知道是不是有用...任意两个探测器之间距离大于半径和那么就可以通过,小于就不能,那么我们可以把不能通过的两个探测器之间连上线,如果探测器覆盖范围到了墙壁,那么这个点和墙壁之间也连上线,后面就只需要判断这些线和墙壁有没有把出口和入口分开了.嗯,然后想到了这个办法:后面的想法有点暴力,那就是把所有的线段交点,包括和墙壁连线的端点都找出来,这里不用管几何的问题,只要管节点相连的问题,这样这个问题就化简成一个图论的问题了.1.从起点开始往外走,每一步看下一个节点和几个节点相连2.如果只和本节点和另一个节点相连,走到这个节点.3.如果下一个节点和两个以上的节点相连,那么将这个节点分成两个,其中一个和其他节点继续相连,另一个只和这个节点和其他相连的点中的一个相连,走到这个节点.用这样的办法就可以把空间完全拆分成两部分,这样的循环结束条件是走到终点或者走回起点,分别对应true/false