algorithm - 检查机器人的给定移动序列是否为圆形

Question

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

G - 走一个单位 L - 左转 R - 右转

输入:路径[] = "GLGLGLG"

输出:给定的移动序列是循环的

这个问题很容易解决:http://www.geeksforgeeks.org/check-if-a-given-sequence-of-moves-for-a-robot-is-circular-or-not/

我的问题是，如果我们只给定了一条特定的路径，而机器人可以无限次地沿该路径移动怎么办。前任:输入:path[]="GL"

所以机器人可以在这条路径上移动 4 次，因此一个循环是可能的。

请提出一些方法来检查给定路径是否可能存在循环。

Answer 1

从起点 (x,y) 和起点方向 d 在 {0,1,2,3} 中执行路径的结果有两个:

1. 从 (x,y) 移动到 (x',y')
2. 改变方向从 d 到 d'

情况一:d == d'

没有方向变化。我们要么离开原点，要么不离开。换句话说:循环当且仅当 (x,y) == (x',y')

情况 2:d == (d' + 2) mod 4

有 180° 方向变化。第二次执行该路径会将完全相同的向量从 (x',y') 移回 (x,y)。循环。

案例 3(最后一个):d == (d' + 1) mod 4 或 d == (d' + 3) mod 4

有一个 90° 的方向变化(顺时针或逆时针)。执行四次路径将围绕“矩形”移动完全相同的矢量，从 (x,y) 到 (x + dx, y + dy)，到 (x + dx - dy, y + dy + dx)，到 ( x + dx - dy - dx, y + dy + dx - dy), to (x + dx - dy - dx + dy, y + dy + dx - dy - dx) = (x, y), 其中 dx = x '-x, dy = y'-y。循环。

因此该算法相当简单:

• 从 (x,y) == (0,0) 和 d = 0 开始模拟路径
• 返回循环 iff d' != 0 || (x',y') == (0,0)