Pythonでロボットが境界ボックス内に留まるかどうかを判定するプログラムの作り方

問題の概要

文字列 s は、ロボットの動きを表す命令列です。ロボットは初期状態として座標 (0, 0) に位置し、北向きを向いています。命令列 s には以下の3種類の文字が含まれます。

• F：現在向いている方向に1単位前進する
• L：その場で左に90度回転する
• R：その場で右に90度回転する

ロボットがこの命令列 s を順番に無限に繰り返し実行するとき、「ロボットが決して外に出ることができない境界ボックス（有界な領域）」が平面上に存在するかどうかを判定するのがこの問題です。

入力例と出力例

入力が s = "FFRFRFFRF" の場合、出力は True になります。ロボットはまず北へ2単位進み、右に90度回転して1ブロック進み、さらに右に90度回転して南へ2単位進み、そして再び右に回転します。この一連の動きが長方形の軌跡（ボックス）を形成するためです。

解法の考え方

この問題のポイントは、命令列を最大4回繰り返せば判定できるという点です。1周分の命令を実行し終えた時点でロボットが原点 (0, 0) に戻っていれば、同じ軌跡を永遠に描き続けるため、明らかに有界です。また、1周後に原点に戻らなくても向きが変化している場合は、数学的に「4周以内に必ず原点へ戻る」ことが証明されています。逆に、1周後に原点に戻らず向きも変わらない場合は、ロボットは直進し続けるため有界にはなりません。

そこで、命令列を4回シミュレートし、各周の終了時に原点にいるかどうかを確認する方針で実装します。

アルゴリズムの手順

• moves := 方向ベクトルの配列 [[0, -1], [1, 0], [0, 1], [-1, 0]] を用意する
• r, c := 0, 0 とする（現在位置）
• d := 0 とする（現在の向きを表すインデックス）
• times を 0 から 3 まで（合計4回）繰り返す
  • i を 0 から s の長さまで繰り返す
    • s[i] が "F" のとき：(r, c) := (r + moves[d][0], c + moves[d][1])
    • s[i] が "L" のとき：d := (d + 3) mod 4
    • s[i] が "R" のとき：d := (d + 1) mod 4
  • r が 0 かつ c が 0 のとき、True を返す
• ループをすべて抜けたら False を返す

Pythonでの実装例

def solve(s):
    moves = [[0, -1], [1, 0], [0, 1], [-1, 0]]
    r, c = 0, 0
    d = 0

    for times in range(4):
        for i in range(len(s)):
            if s[i] == "F":
                r, c = r + moves[d][0], c + moves[d][1]
            elif s[i] == "L":
                d = (d + 3) % 4
            elif s[i] == "R":
                d = (d + 1) % 4
        if r == 0 and c == 0:
            return True
    return False

s = "FFRFRFFRF"
print(solve(s))

入力

"FFRFRFFRF"

出力

True

計算量

• 時間計算量：O(|s|)（命令列を4回走査するため O(4×|s|)、定数倍を除けば線形時間）
• 空間計算量：O(1)（追加の記憶領域は定数のみ）