BAI4 HSGHN L12 V1 2019-2020

#define task "BAI4"

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e5 + 5;
int x[] = {0, 0, 1, -1},
    y[] = {1, -1, 0, 0};

int d[N];
string s;
vector<int> adj[N];
vector<pair<int, int>> v;

void Read()
{
    cin >> s;
}

int Get(char x)
{
    switch (x)
    {
    case 'D':
        return 0;
    case 'T':
        return 1;
    case 'N':
        return 2;
    case 'B':
        return 3;
    }
    return -1;
}

void Solve()
{
    /* Make Graph */
    pair<int, int> now = {0, 0};
    v.emplace_back(now);

    for (auto i : s)
    {
        now = {now.first + x[Get(i)], now.second + y[Get(i)]};
        v.emplace_back(now);
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());

#define Find(x, v) (lower_bound(x.begin(), x.end(), v) - x.begin() + 1)

    now = {0, 0};

    for (auto i : s)
    {
        int j = Find(v, now);
        now = {now.first + x[Get(i)], now.second + y[Get(i)]};
        int t = Find(v, now);

        adj[j].emplace_back(t);
        adj[t].emplace_back(j);
    }

    /* Calculate Shortest Path using BFS */

    d[Find(v, now)] = 1;
    queue<int> q({Find(v, now)});
    now = {0, 0};
    int piv = Find(v, now);

    while (!q.empty())
    {
        int c = q.front();
        q.pop();

        if (c == piv)
        {
            cout << d[c] - 1;
            return;
        }

        for (auto i : adj[c])
            if (!d[i])
            {
                d[i] = d[c] + 1;
                q.emplace(i);
            }
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();
    Solve();
}