Aak*_*ain 5 algorithm geometry dynamic-programming computational-geometry
采访中有人问我这个问题，但我解决不了。
如果您能帮助我解决问题，我将不胜感激。
问题如下：
您将得到一个矩形区域，其左和最底层的坐标为（0,0）和最右边和最上面的坐标为（X，Y） 。
有Ñ具有给定中心圆坐标即内侧的区域都具有相同的半径存在“R”。
您目前站在（0,0），想达到（x，y）而没有碰任何圆圈。
您必须告诉是否可能。
他告诉我，您可以在2个点之间自由移动，而不必沿x轴或y轴移动。
我想到的解决方案包括获取x * y维度的矩阵，并为每个圆标记位于其内部或触摸它的点。
之后，BFS从（0,0）开始应用，以检查是否可以达到（x，y）。
他告诉我BFS会错的，我不知道为什么。
我曾以为，圆为整数半径和具有整数坐标。
他还要求我在没有这些假设的情况下解决问题。
我不能 当被问到时，他告诉我这是一个标准问题，我应该可以在google上找到它。
我不能，再次。请帮忙！
我认为两个圆只有在其中心之间的距离小于 2r 时才能阻挡路径。因此，构建重叠圆的“岛”并检查是否有任何岛阻挡了从 0 到 (x,y) 的路径，即其中的任何圆是否与矩形边界相交，使得这些交点之间的直线相交就足够了点会阻塞路径。