C++でマトリックス内の最終セル位置を求める方法

文字列として一連のコマンドが与えられているとします。この文字列には、4つの方向を表す4種類の文字が含まれています。Uは上、Dは下、Lは左、Rは右を意味します。さらに、オブジェクトの初期セル位置 (x, y) も与えられます。与えられたコマンド列に従った後の、マトリックス内におけるオブジェクトの最終的なセル位置を求めるのが目的です。なお、最終的なセル位置は必ずマトリックス内に存在するものと仮定します。

例として、コマンド文字列が「DDLRULL」、初期位置が (3, 4) である場合を考えてみましょう。このとき、最終位置は (1, 5) となります。

アルゴリズムの考え方

アプローチは非常にシンプルです。まず、コマンド文字列内に出現する上・下・左・右の各移動の回数を数えます。その後、次の式を用いて最終位置 (x', y') を計算します。

(x', y') = (x + 右の回数 − 左の回数, y + 下の回数 − 上の回数)

左右の移動は x 座標に影響し、上下の移動は y 座標に影響するため、それぞれの差分を初期座標に加算するだけで最終位置が求まります。

実装例

#include<iostream>
using namespace std;
void getFinalPoint(string command, int x, int y) {
    int n = command.length();
    int count_up, count_down, count_left, count_right;
    int x_final, y_final;
    count_up = count_down = count_left = count_right = 0;
    for (int i = 0; i < n; i++) {
        if (command[i] == 'U')
            count_up++;
        else if (command[i] == 'D')
            count_down++;
        else if (command[i] == 'L')
            count_left++;
        else if (command[i] == 'R')
            count_right++;
    }
    x_final = x + (count_right - count_left);
    y_final = y + (count_down - count_up);
    cout << "Final Position: " << "(" << x_final << ", " << y_final << ")";
}
int main() {
    string command = "DDLRULL";
    int x = 3, y = 4;
    getFinalPoint(command, x, y);
}

出力結果

Final Position: (1, 5)

このプログラムでは、文字列を一度走査するだけで各方向の移動回数を集計できるため、時間計算量は O(n)、空間計算量は O(1) となります。コマンド文字列が長くなっても効率的に最終位置を求められる点が、このアルゴリズムの利点です。