Foobar带枪到护卫战斗优化

Question

我正在思考挑战谷歌Foobar的“带枪到卫队战斗” (也定义在问题的底部，以便于使用)。

我在这篇文章中得出了同样的结论，那就是最好通过反思房间来解决这个问题。然而，本文建议我们首先生成一个镜像房间的盒子，其中高度和宽度由我们可以在炮距(ceil((player_position + laser distance) / room_size))内向上和横向反射房间的最大次数来定义。然后，我们将移除所有对角线在盒子外的部件。

然而，这很容易导致效率低下，因为我们必须产生比火炮距离允许的更多的点数。随着炮距的增加，这种低效率会增加。

但是，我找不到解决这个问题的办法。生成问题点的最佳方法是什么？

=============================== 呃-哦-你被兰巴指挥官的精英卫兵逼得走投无路！幸运的是，在你穿过车站的时候，你从一个废弃的岗哨抓起了一件横梁武器，所以你有机会奋力逃出。但是横梁武器对你和精英守卫都是潜在的危险:它的横梁反射墙壁，这意味着你必须非常小心你射击的地方，以避免弹向你自己！ 幸运的是，横梁只能通过一定的最大距离，然后变得太弱而不会造成损害。你也知道，如果一个光束击中一个角落，它会反弹回来，完全相同的方向。当然，如果光束击中你或守卫，它将立即停止(尽管痛苦)。 编写一个函数解(维度、your_position、guard_position、距离)，给出一个由2个整数组成的房间宽度和高度的数组，一个由房间中x和y坐标的2个整数组成的数组，一个由房间内守卫的x和y坐标的2个整数组成的数组，并返回一个整数，表示在光束可以通过的最大距离下，可以发射的不同方向数的整数。 房间的整数维为1< x_dim <= 1250，1< y_dim <= 1250。你和精英守卫都位于房间内不同位置(x，y)的整数格上，使得0例如，如果您和精英警卫的位置是在第3、2、your_position 1、1、guard_position 2、1和最大射击距离为4的房间中，您可以朝七个不同的方向射击，以击中精英警卫(作为矢量方位从您的位置给出)：1、0、1、2、2、3、2、2、-3、2和-3、-2。作为具体的例子，方位1，0的射门是距离1的直线水平射击，方位-3，-2的射门从左墙反弹，然后在击打精英护卫前的底部墙，总射门距离为平方吨(13)，而对方位1，2的射门只从顶墙反弹，然后以总射门距离(5)击中精英护卫。 测试用例==========您的代码应该通过以下测试用例。请注意，它也可能针对此处未显示的隐藏测试用例运行。 Python案例 输入: solution.solution(3, 2，1，2，1，4)输出:7 输入: solution.solution(300,275,150,185,100,500)输出:9

Answer 1

生成下一个房间只是在一个选择的方向上映射它。我们有两个新的积分，一个是后卫，一个是我们自己。我们可以把它作为一个迭代，一个房间一个房间，有固定的空间和时间。一种对我有用的方法(虽然对代码来说并不简单)就是散列(从原点到新镜像警卫)，因为我们需要能够确定新的点是否位于我们已经发射过的线路上，并与其他一些检查一起命中了警卫线。

另外，由于我们逐个房间穿行，所以当距离太远时，我们可以停下来，而不会产生额外的房间。

至少有一个已经发布的代码看起来比我建议的要紧凑得多，但我不明白。看起来它是在概括转换，但我无法遵循它。

Answer 2

ceil((player_position + laser distance) / room_size)是不够的

在下列情况下：

solution([20, 20], [2, 2], [2, 4], 5)

您仍然需要为左侧创建一个反射。

我发现这个公式效果更好：

x_reflect = max(int(float(your_position[0] + distance) / dimensions[0]), abs(int(floor(float(your_position[0] - distance) / dimensions[0]))))
y_reflect = max(int(float(your_position[1] + distance) / dimensions[1]), abs(int(floor(float(your_position[1] - distance) / dimensions[1]))))

我会把它写成评论，但我没有足够的观点