在具有障碍物的二维平原中寻找路径
我正在尝试解决我已经给出的编程任务,而且我没有任何想法如何去做.
这就是问题:
Skinny Pete受邀参加花园生日派对.他并不太喜欢派对,但听说生日蛋糕真是太棒了,他不想错过尝试它的机会.
只有一个小问题.在花园里安装了一个喷水灭火系统,通过了解他的朋友,很有可能有人将其作为派对恶作剧.皮特喜欢蛋糕,但真的不喜欢弄湿.幸运的是,他发现了一个花园的草图,其中有喷头的位置以及每个人可以洒多少水.
- 花园看起来像一个矩形,一面开放,房子在对面.
- 蛋糕将在房子里.
- 另外两边有围栏,所以不能通过那里进入,房子没有后门.皮特有兴趣知道是否有可能进入花园并进入房屋而没有任何被淋湿的风险.
为简单起见,我们可以认为花园的地图是笛卡尔坐标系.
花园是一个矩形,其边与轴平行,左下角在原点(0,0).
花园的入口是左侧,房子位于右侧.
洒水器表示为具有中心和半径的圆.走进这样一个圆圈内的任何地方可能会让你感到湿透.
出于这个问题的目的,由于皮特太瘦了,我们可以把他想象成一个在太空中旅行的点,用实数作为坐标.
输入规格标准输入的第一行包含两个空格分隔的整数H和W,即花园的高度和宽度.
下一行包含喷头N的数量.之后N行跟随有三个空格分隔的整数 - Xi,Yi和Ri.这是一个喷水器的描述,作为一个圆心,中心(Xi,Yi)和半径Ri.
1≤N≤128
1≤H,W≤1024
0≤Xi≤W
0≤Yi≤H
1≤Ri≤1024
输出规格
输出包含"CAKE"(不带引号)的单行,如果可以在不弄湿的情况下到达房屋,否则输出"NO CAKE"(不带引号).
提前感谢帮助者
既然你没有显示任何代码而你只是暗中寻求帮助,我会给出一个关键的想法,并将数学和实现留给你.
除非在花园的底部和顶部之间有一连串的洒水圈,否则 Skinny Pete可以在不弄湿的情况下获得蛋糕.换句话说,我们可以假设皮特成功了.但请浏览所有圈子.我们看到是否有任何圆与花园的底边相交 - 这很容易数学.如果没有,皮特真的成功了.如果有,看看是否有另一个圆与第一个圆相交,那么是否有另一个圆与第二个圆相交,等等.最后,你看看这个链中的最后一个圆是否与花园的顶边相交.如果有任何这样的交叉圆链也与花园的顶部和底部相交,那么可怜的皮特就会挨饿.(请注意,只有一个与顶部和底部相交的圆圈也会让Pete感到沮丧 - 认为这是一个链条.)
下面是您的比赛PDF中的第二个示例图,其中您可以看到没有跨越圈子链,因此Pete成功.
这是Pete失败的第三个例子的图表.请注意,左侧有一个四个圆圈,颜色为蓝色,横跨花园.
鉴于这个想法,有一个明显的O(N^2)算法来找到所有相交的圆对和一个O(N)算法,找到与花园的顶部和底部相交的圆.您可以使用图论中的路径查找算法来解决您的问题.将顶部和底部以及圆圈视为图中的节点,如果它们相交,则两个节点与边连接.然后,您可以在表示顶部和底部的节点之间搜索路径.
祝你好好理算数学,算法和代码.