【C++】指定された方向に移動した後、開始位置(0,0)に戻れるかどうかを判定する方法

平面上の座標 (0, 0) を起点として、4種類の文字で構成された文字列が与えられます。この文字列は連続する移動方向を表しており、各文字は以下の方向に対応しています。

• E:東(east)
• W:西(west)
• N:北(north)
• S:南(south)

この問題では、与えられたすべての移動指示を実行した後、再び開始位置 (0, 0) に戻ることができるかどうかを判定します。

具体例

たとえば入力が "EENWWS" の場合、出力は true になります。移動の流れを追うと以下のようになります。

• 東へ2単位移動(E、E)
• 北へ1単位移動(N)
• 西へ2単位移動(W、W)
• 南へ1単位移動(S)

東西方向の移動が相殺され、南北方向の移動も相殺されるため、最終的に元の位置に戻ることになります。

解法のアプローチ

この問題は非常にシンプルなカウンタ管理で解決できます。考え方は次のとおりです。

• 文字列の長さを l とします。l が 0 の場合は移動がないため true を返します。
• 水平方向の変位を表す lft と、垂直方向の変位を表す up をそれぞれ 0 で初期化します。
• 文字列を先頭から順に走査し、各文字に応じてカウンタを更新します。
  • 'W' なら lft を +1
  • 'E' なら lft を -1
  • 'N' なら up を +1
  • 'S' なら up を -1
• 走査終了後、lft と up がどちらも 0 であれば true、そうでなければ false を返します。

つまり、「東西の移動回数が一致し、かつ南北の移動回数も一致していれば原点に戻れる」という性質を利用しています。

C++による実装例

以下に実際の実装を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool solve(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] == 'W') {
                lft++;
            }
            if (moves[i] == 'E') {
                lft--;
            }
            if (moves[i] == 'N') {
                up++;
            }
            if (moves[i] == 'S') {
                up--;
            }
        }
        if (lft == 0 && up == 0) {
            return true;
        }
        return false;
    }
};
main(){
    Solution ob;
    cout << (ob.solve("EENWWS"));
}

入力

"EENWWS"

出力

1

出力が 1(true)となり、開始位置に戻れることが確認できました。

計算量について

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n)(n は文字列の長さ)、使用する追加メモリは定数個の変数のみなので空間計算量は O(1) となります。非常に効率的な解法です。