C++で一連の移動後のロボットの最終位置を求める

問題概要

この問題では、上下左右の4方向に移動できるロボットが与えられます。方向は上（'U'）、下（'D'）、左（'L'）、右（'R'）の4種類です。また、これらの方向の頭文字からなる移動指示の文字列が与えられます。ロボットの初期位置を (0, 0) としたとき、一連の移動をすべて実行した後の最終位置を出力することが課題です。

例で問題を理解しよう

入力 − 'LDRRUL'

出力 − (0, 0)

説明 − 各移動ごとの座標の変化は以下の通りです。

L（左） : (0,0) → (-1,0)
D（下） : (-1,0) → (-1,-1)
R（右） : (-1,-1) → (0,-1)
R（右） : (0,-1) → (1,-1)
U（上） : (1,-1) → (1,0)
L（左） : (1,0) → (0,0)

このように、左と右・上と下の移動が打ち消し合うため、最終的に元の位置 (0, 0) に戻ります。

解法のアプローチ

この問題を効率的に解くには、x軸方向とy軸方向それぞれの移動量を集計します。

• x座標：「右（R）」の移動でカウントを +1、「左（L）」の移動で -1 します。
• y座標：「上（U）」の移動でカウントを +1、「下（D）」の移動で -1 します。

文字列を先頭から順に走査して合計値を求めれば、それがそのままロボットの最終座標になります。計算量は文字列の長さを n とすると O(n)、追加のメモリは不要で O(1) という非常にシンプルなアルゴリズムです。

実装例

上記の解法を C++ で実装したプログラムを以下に示します。なお、変数は必ず 0 で初期化してください。未初期化のまま使用すると不定値（ガベージ値）が出力されてしまいます。

#include <iostream>
#include <string.h>
using namespace std;
void robotMoved(string move) {
    int xAxis = 0, yAxis = 0;
    int l = move.size();
    for (int i = 0; i < l; i++) {
        if (move[i] == 'U')
            yAxis++;
        else if (move[i] == 'D')
            yAxis--;
        else if (move[i] == 'L')
            xAxis--;
        else if (move[i] == 'R')
            xAxis++;
    }
    cout << "ロボットの最終位置は : (" << xAxis << ", " << yAxis << ")" << endl;
}
int main() {
    string move = "URLLDDRRUDUDDRU";
    robotMoved(move);
    return 0;
}

出力

ロボットの最終位置は : (2, -1)

まとめ

本記事では、移動指示の文字列からロボットの最終位置を求める問題を取り上げました。各方向の出現回数を x 軸・y 軸ごとに加減算するだけで答えが得られるため、直感的かつ高速に解けるのがポイントです。競技プログラミングでも頻出のパターンなので、ぜひマスターしておきましょう。