algorithm - 检查是否存在圆

Question

我在一次 Google 面试中被问到这个问题。我们得到一个由字母 F、L、R 组成的字符串。 - 这是机器人遵循的指令

F-前进一步。

左转。

R- 右转。

字符串长度最多可达 2500 个字符。

字符串自身运行无限次。我们需要判断是否存在一个半径为 r(r 可以是任何实数)的圆，这样机器人就不会离开圆。我被困在这一点上。我想到了使用凸包，但是如何无限次检查它。将不胜感激用代码解释。请帮忙。提前致谢

Answer 1

1. 每次运行(一次运行执行给定字符串的所有命令一次)会改变两件事:机器人注视的方向和它的位置(也就是说，每次运行都会将它移动某个向量(这个向量的方向取决于在运行前的初始方向上)并旋转它)。

2. 可能的方向数为 4。因此，在运行模拟 4 次后，它看起来与最初的方向相同(每次摩擦都将其旋转相同的角度)。

3. 这就是为什么 4 次连续运行只是将它移动某个向量而不进行任何旋转。

4. 因此，我们可以连续运行模拟 4 次，看看它是否停在原点。如果是，我们可以找到包含其路径的最小圆。否则，不存在这样的圈子。