algorithm - 在有障碍物的二维平原上寻找路径

Question

我正在尝试解决交给我的编程任务，但我完全不知道该怎么做。

问题是:

Skinny Pete is invited to a garden birthday party. He doesn’t really like parties too much, but heard that the birthday cake is going to be really amazing and he wouldn’t like to miss the chance to try it.

There is only one little problem. There is a sprinkler system installed in the garden and by knowing his friends, there is a high chance of someone turning it on as a party prank. Pete likes cake, but really hates getting wet. Luckily he found a sketch of the garden that has the location of the sprinklers and how far each one can sprinkle water.

• The garden looks like a rectangle that is open on one side and has the house in the opposite side.
• The cake is going to be in the house.
• The other two sides have fences so one can not enter through there, and the house does not have a back entrance. Pete is interested to know if it is possible to enter the garden and get to the house without any risk of getting wet.

For simplicity we can think that the map of the garden is in Cartesian coordinate system.

• The garden is a rectangle that has sides parallel to the axes and having its bottom left corner at the origin (0, 0).

• The entrance to the garden is the left side and the the house is at the right side.

• Sprinklers are represented as circles with a center and a radius. Stepping anywhere inside such a circle might get you wet.

• For the purpose of this problem, and since Pete is so skinny, we can think of him as just a point travelling in the space, with real numbers as coordinates.

Input Specifications First line of the standard input contains two space separated integers H and W, the height and the width of the garden.

Next line contains the number of sprinklers N. After that N lines follow having three space separated integers each - Xi, Yi and Ri. This a description of a sprinkler as a circle with center (Xi, Yi) and radius Ri.

1 ≤ N ≤ 128

1 ≤ H, W ≤ 1024

0 ≤ Xi ≤ W

0 ≤ Yi ≤ H

1 ≤ Ri ≤ 1024

Output Specifications

Output a single line containing “CAKE” (without quotes) if it is possible to get to the house without getting wet and “NO CAKE”(without quotes) otherwise.

在此先感谢帮助者

Answer 1

由于您没有显示任何代码，您只是含蓄地寻求帮助，所以我将给出一个关键思想并将数学和实现留给您。

瘦皮特可以在不弄湿的情况下得到蛋糕，除非在花园的底部和顶部之间有一连串的洒水环。换句话说，我们可以假设皮特成功了。但是看遍所有的圈子。我们看看是否有任何圆圈与花园的底部边缘相交——这是简单的数学运算。如果没有，皮特真的成功了。如果有，看看是否有另一个圆圈与第一个圆圈相交，然后是否有另一个圆圈与第二个圆圈相交，依此类推。最后，您查看此链中的最后一个圆圈是否与花园的顶部边缘相交。如果有任何这样的相交圆链也与花园的顶部和底部相交，可怜的皮特就会饿死。 (请注意，只有一个与顶部和底部相交的圆圈也会让皮特感到沮丧——将其视为一连串的圆圈。)

这是比赛 PDF 中第二个示例的图表，您可以在其中看到没有跨圈链，因此 Pete 成功了。

这是第三个示例的图表，Pete 失败了。请注意，左侧有一个由四个圆圈组成的链条，颜色为蓝色，横跨花园。

根据这个想法，显然有一个O(N^2) 算法可以找到所有相交圆对，还有一个O(N) 算法可以找到圆与花园的顶部和底部相交。您可以使用图论中的寻路算法来解决您的问题。将顶部和底部以及您的圆圈视为图中的节点，如果两个节点相交，则两个节点与一条边相连。然后，您搜索代表顶边和底边的节点之间的路径。

祝你在计算数学、算法和代码时好运。