python - 环形路线测试问题

Question

这是问题陈述，我找到了两个不同的解决方案，发布问题陈述和解决方案，我的问题是，想知道是否有必要检查连续运行4次是否会产生圆圈？为什么要检查 4 次连续运行，而不是其他数字——比如 3 次连续运行？谢谢。

问题陈述

给定机器人的一系列移动，检查该序列是否为圆形。如果机器人的第一个和最后一个位置相同，则一系列移动是循环的。移动可以是以下之一。

  G - Go one unit
  L - Turn left
  R - Turn right 

例子:

Input: path[] = "GLGLGLG"
Output: Given sequence of moves is circular 

Input: path[] = "GLLG"
Output: Given sequence of moves is circular 

解决方案一

http://www.geeksforgeeks.org/check-if-a-given-sequence-of-moves-for-a-robot-is-circular-or-not/

方案二

Check If there exists a Circle

提前致谢，林

Answer 1

解决方案 1 和解决方案 2 似乎适用于不同的问题。两者都涉及机器人进行一系列 Action ，但解决方案 2 的问题是让机器人重复该序列 无限 次。

• 问题 1. 运行序列一次。机器人在初始位置吗？

• 问题2.如果序列无限运行，机器人的路线是否可以包含在有限圆内？

第二个问题似乎更有趣，所以我在这里重点讨论。

如解决方案 2 中所述，单次运行有两种效果:旋转(机器人最终面对的方向)和位移(机器人移动到新位置)。

旋转一般分为三种类型:

• 无旋转。在这种情况下，您只需运行 1 次即可解决问题。

  • 如果位移为零，则可以包含无限次游程有限圆。您只需要绘制机器人的完整路线并计算需要那个圆的大小。

  • 如果位移不为零，则无限次运行会导致无限次位移，因此不能包含在有限圆中。

• 90 度旋转(即向左或向右一次)。在这个情况下，您需要运行 4 次。之后，你会回到最初方向，您可以使用描述的相同逻辑解决问题无轮换情景。

• 旋转 180 度(即向左或向右旋转两次)。在这个在这种情况下，您需要运行 2 次才能回到初始方向。解决以同样的方式。