HA_61_Moves

#include <iostream>
#include <vector>
#include <map>
#include <utility>

using namespace std;

struct Coord {
    int x;
    int y;
    bool operator<(const Coord& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

// Элемент пути: координата и ход,
// который привёл сюда (для начальной — '\0')
struct Step {
    Coord pos;
    char move;
};

class PathSimplifier {
public:
    static vector<char> removeLoops(const vector<char>& moves) {
        vector<Step> path; // текущий путь с учётом сохранения немедленных обратных
        map<Coord, int> last_occurrence; // последняя позиция этой координаты в path

        Coord curr{0, 0};
        path.push_back(Step{curr, '\0'});
        last_occurrence[curr] = 0;

        for (char mv : moves) {
            Coord next = applyMove(curr, mv);

            auto it = last_occurrence.find(next);
            bool is_immediate_reverse = false;
            if (!path.empty() && path.size() >= 2) {
                // предыдущая позиция перед curr
                Coord prev = path[path.size() - 2].pos;
                if (next.x == prev.x && next.y == prev.y) {
                    is_immediate_reverse = true;
                }
            }

            if (it != last_occurrence.end() && !is_immediate_reverse) {
                int prev_idx = it->second;
                // Если повторное вхождение не является
                // немедленным возвратом и это не просто next == curr
                if (prev_idx != (int)path.size() - 2) {
                    // Длинная петля: обрезаем всё после prev_idx
                    for (int i = (int)path.size() - 1; i > prev_idx; --i) {
                        last_occurrence.erase(path[i].pos);
                        path.pop_back();
                    }
                    // curr становится next (уже в path[prev_idx]); не добавляем mv
                    curr = next;
                    continue;
                }
            }

            // Обычный шаг или немедленный обратный — добавляем
            path.push_back(Step{next, mv});
            last_occurrence[next] = (int)path.size() - 1;
            curr = next;
        }

        vector<char> result;
        for (size_t i = 1; i < path.size(); ++i) {
            result.push_back(path[i].move);
        }
        return result;
    }

private:
    static Coord applyMove(const Coord& c, char mv) {
        Coord res = c;
        switch (mv) {
            case 'U': res.y += 1; break;
            case 'D': res.y -= 1; break;
            case 'L': res.x -= 1; break;
            case 'R': res.x += 1; break;
            default: break;
        }
        return res;
    }
};

int main() {
    vector<char> moves = {'D','R','D','R','R','U','L','L','U','R','L','R'};
    vector<char> simplified = PathSimplifier::removeLoops(moves);

    cout << "Array: ";
    for (char c : moves) cout << c << ' ';
    cout << "\nWithout loops: ";
    for (char c : simplified) cout << c << ' ';
    cout << "\n";
    return 0;
}