AtCoder ABC 291 C - LRUD Instructions 2 (4Q, 灰色, 300 点)

set の練習！

• 問題へのリンク

問題概要

二次元平面上に高橋君がいる。高橋君は原点から移動を 回行った。

回の移動は長さ の文字列で表される。各文字は L（左へ移動）、R（右へ移動）、U（上へ移動）、D（下へ移動）のいずれかである。

高橋君が同じ座標にいたことがあるかどうかを判定せよ。

制約

• 

考えたこと

高橋君の移動は 2 つの整数値 によって管理できる。初期状態では高橋君は原点にいるため

である。高橋君の移動過程で、次のデータを管理しよう。

---

set<pair<int,int>> 型変数 already：高橋君がすでに訪れた座標を格納する集合

---

これを用いて、高橋君が新たに訪れた座標が「すでに訪れたことがあるかどうか」を判定できる。

計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    string S;
    cin >> N >> S;

    int x = 0, y = 0;
    set<pair<int,int>> already;
    already.insert(make_pair(x, y));
    for (auto c : S) {
        if (c == 'L') x--;
        else if (c == 'R') x++;
        else if (c == 'U') y++;
        else y--;

        if (already.count(make_pair(x, y))) {
            // すでに訪れているとき
            cout << "Yes" << endl;
            return 0;
        }

        // 最新の座標を集合 already に格納する
        already.insert(make_pair(x, y));
    }
    cout << "No" << endl;
}