20472: 死循环的机器人

http://cs101.openjudge.cn/practice/20472/

在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。机器人可以接受下列三条指令之一： "G"：直走 1 个单位 "L"：左转 90 度 "R"：右转 90 度机器人按顺序执行指令，并一直重复它们。只有在平面中存在死循环使得机器人永远无法离开时，返回 1。否则，返回 0。

输入

由G L R组成的字符串

输出

如果存在死循环输出1，否则0

样例输入

GGLLGG

样例输出

提示

样例中的机器人会在长度为4的直线徘徊(本来打错成2)

模拟机器人的移动，并检查它是否最终会回到原点并面向原来的方向，因为这是死循环的必要条件。如果在执行一系列指令后，机器人回到原点并且面向原来的方向，那么它将循环执行同样的指令序列，形成一个循环。

下面是一个 Python 函数，它实现了这个逻辑：

python

def is_robot_making_loop(commands):
    # 初始位置和方向
    x, y = 0, 0
    direction = 'N'

    # 方向变换的规则，用字典表示
    left_turns = {'N': 'W', 'W': 'S', 'S': 'E', 'E': 'N'}
    right_turns = {'N': 'E', 'E': 'S', 'S': 'W', 'W': 'N'}

    # 模拟机器人的移动
    for command in commands:
        if command == 'G':
            if direction == 'N':
                y += 1
            elif direction == 'S':
                y -= 1
            elif direction == 'E':
                x += 1
            elif direction == 'W':
                x -= 1
        elif command == 'L':
            direction = left_turns[direction]
        elif command == 'R':
            direction = right_turns[direction]

    # 如果机器人回到原点，或者不是面向北方（说明它会改变方向然后可能回到原点）
    return (x == 0 and y == 0) or direction != 'N'

# 读取输入并输出结果
commands = input().strip()
print(1 if is_robot_making_loop(commands) else 0)

这个函数首先定义了机器人的初始位置和方向。然后，它根据指令移动机器人，并在完成所有指令后检查机器人的位置和方向。

如果机器人回到了原点 (0, 0) 并且方向不是北（意味着它改变了方向并且可能在执行更多指令后回到原点），函数返回 True。
如果机器人没有回到原点，或者回到原点时方向是北（意味着它将沿直线移动而不是循环），函数返回 False。

最后，程序读取用户输入的指令，调用函数，并输出相应的结果，如果存在死循环输出 1，否则 0。

python

def is_robot_making_loop(commands):
    # 初始位置和方向
    x, y = 0, 0
    # 方向变换的规则，用列表表示，0=N, 1=E, 2=S, 3=W
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    # 初始方向北
    dir_index = 0

    # 模拟机器人的移动
    for command in commands:
        if command == 'G':
            # 沿着当前方向前进一步
            x += directions[dir_index][0]
            y += directions[dir_index][1]
        elif command == 'L':
            # 左转90度就是方向列表中的前一个方向
            dir_index = (dir_index - 1) % 4
        elif command == 'R':
            # 右转90度就是方向列表中的下一个方向
            dir_index = (dir_index + 1) % 4
    
    # 如果机器人回到原点，或者方向发生改变（不再是北），则会形成循环
    return (x == 0 and y == 0) or (dir_index != 0)

# 读取输入并输出结果
commands = input().strip()
print(1 if is_robot_making_loop(commands) else 0)

20472: 死循环的机器人 ​

20472: 死循环的机器人