C++で解く「円に閉じ込められたロボット」問題 ― 有界な動きの判定アルゴリズム

無限に広がる平面上に、初期位置 (0, 0) で北を向いて立つロボットがあります。このロボットは次の3種類の命令を受け取ることができます。

• G … 現在向いている方向へ1単位まっすぐ進む
• L … 左に90度回転する
• R … 右に90度回転する

ロボットは与えられた命令列を順に実行した後、同じ命令列を永遠に繰り返します。ここで、平面上に「ロボットが二度と外に出ない円」が存在するかどうかを判定します。

例えば入力が "GGLLGG" の場合、答えは true になります。ロボットは (0, 0) から (0, 2) へ移動した後、元の位置と向きに戻る閉じた経路に入り、以後その領域を永遠に周回し続けるためです。

解き方のアプローチ

この問題は次の手順で解くことができます。

• 方向ベクトルの配列 dir = [[0,1], [1,0], [0,-1], [-1,0]](北・東・南・西の順)を用意する
• 現在位置を表すペア temp を (0, 0)、方向インデックス k を 0 で初期化する
• 文字列 s の各文字について以下を処理する
  • s[i] が 'G' のとき:temp を (dir[k][0], dir[k][1]) だけ進める
  • s[i] が 'L' のとき:k = (k - 1 + 4) mod 4(反時計回り)、'R' のとき:k = (k + 1) mod 4
• 1サイクル完了後、temp が (0, 0) に戻っている、または k > 0(向きが北から変わっている)なら true、そうでなければ false を返す

なぜこれで判定できるのか

1サイクル後に原点へ戻っていれば、ロボットは明らかに有限の範囲にとどまります。また、位置が原点に戻らなくても向きが変わっていれば、数サイクル以内に必ず元の位置へ戻り、軌跡は有限の円内に収まります。逆に、位置も向きも最初と同じままなら、ロボットは毎サイクル北へまっすぐ進み続けるため、無限遠へと離れていきます。

C++による実装例

理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
// 北・東・南・西の順に方向ベクトルを定義
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
class Solution {
    public:
    bool isRobotBounded(string s) {
        pair <int, int> temp({0,0});
        int k = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == 'G'){
                temp.first += dir[k][0];
                temp.second += dir[k][1];
            }else if(s[i] == 'L'){
                k = ((k - 1) + 4) % 4; // 左回転
            }else{
                k = (k + 1) % 4; // 右回転
            }
        }
        // 原点に戻った、または向きが変わっていれば有界
        return (temp.first == 0 && temp.second == 0) || k > 0;
    }
};
main(){
    Solution ob;
    cout << (ob.isRobotBounded("GGLLGG"));
}

入力

"GGLLGG"

出力

1

計算量は、命令列の長さを n とすると時間 O(n)、空間 O(1) となり、非常に効率的な解法です。