【C++】ロボットが移動後に原点(0,0)へ戻るかどうかを判定するアルゴリズム

あるロボットがあり、その初期位置は (0, 0) だとします。ここで、ロボットの一連の移動手順が与えられたとき、すべての移動を完了した後、このロボットが元の位置 (0, 0) に戻っているかどうかを判定する必要があります。

移動の手順は文字列として与えられ、moves[i] が i 番目の移動を表します。各記号の意味は以下の通りです。

• R：右へ移動
• L：左へ移動
• U：上へ移動
• D：下へ移動

ロボットがすべての移動を終えた時点で原点に戻っていれば true を返し、そうでなければ false を返します。

たとえば、入力が "RRULLD" の場合、出力は true になります。これは、右へ2単位進み、次に上へ移動し、その後左へ2単位、最後に下へ移動することで、元の開始位置に戻るためです。

解決のためのアプローチ

この問題を解くには、以下の手順に従います。

1. 変数 l に移動文字列の長さを代入します。
2. l が 0 の場合（移動がない場合）は、true を返します。
3. 水平方向のカウンタ lft と垂直方向のカウンタ up をそれぞれ 0 で初期化します。
4. i = 0 から i < l の間、以下の処理を繰り返します。
   • moves[i] が 'L' なら、lft を 1 増やす
   • moves[i] が 'R' なら、lft を 1 減らす
   • moves[i] が 'U' なら、up を 1 増やす
   • moves[i] が 'D' なら、up を 1 減らす
5. ループ終了後、lft が 0 かつ up が 0 であれば true を返します。
6. それ以外の場合は false を返します。

この方法では、左右の移動が打ち消し合い、上下の移動も打ち消し合うことがカウンタによって確認できます。計算量は O(n)、空間計算量は O(1) と非常に効率的です。

実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool judgeCircle(string moves) {
      int l = moves.length();
      if (l == 0) {
         return true;
      }
      int lft = 0, up = 0;
      for (int i = 0; i < l; i++) {
         if (moves[i] == 'L') {
            lft++;
         }
         if (moves[i] == 'R') {
            lft--;
         }
         if (moves[i] == 'U') {
            up++;
         }
         if (moves[i] == 'D') {
            up--;
         }
      }
      if (lft == 0 && up == 0) {
         return true;
      }
      return false;
   }
};
main(){
   Solution ob;
   cout << (ob.judgeCircle("RRULLD"));
}

入力

"RRULLD"

出力

1

出力が 1（つまり true）となり、ロボットが正しく原点に戻ったことが確認できます。