данный код не проходит time limit в 2 секунды. Ско...

Где «заседает» время

1. Конструктор Graph

   cpp
   do {
       state_ind_[asc_] = ind;
       ind_state_[ind] = asc_;
   } while (std::next_permutation(asc_.begin(), asc_.end()));

   • 362 880 вызовов std::next_permutation.
   • Для каждой перестановки два вставления в unordered_map со строковым ключом (хэш-функция + динамическое выделение памяти для std::string).
     Это уже десятки миллионов мелких операций и сотни мегабайт аллокаций на горячем пути: за 2 с не успевает.

2. Поиск в картах во время BFS
   Внутри цикла:

   cpp
   int neigh = state_ind_.at(next.first);      // hash(string) каждую итерацию
   const std::string& cur_state = ind_state_.at(v);

   BFS для самой «дальней» начальной позиции посещает ≈ 180 000 вершин, т.е. ещё сотни тысяч обращений к тем же unordered_map + копирование строк-состояний.

3. adj_ не используется, но инициализируется
   std::vector<std::vector<Gambit>> adj_(kPermNum) создает 362 880 пустых std::vector-ов — лишние ~9 МБ памяти и время на конструкторы.

---

Как починить за < 2 с

1. Избавиться от unordered_map и строк

Представим перестановку как число от 0 до 362 879 при помощи кодов Лемера (Cantor).

cpp
constexpr int fact[10] = {1,1,2,6,24,120,720,5040,40320,362880};

int encode(const std::array<char,9>& a) {          // O(9^2) &asymp; 81 операций
    int res = 0;
    bool used[9] = {};
    for (int i = 0; i < 9; ++i) {
        int cnt = 0;
        for (int d = 0; d < a[i]-'0'; ++d) if (!used[d]) ++cnt;
        res += cnt * fact[8-i];
        used[a[i]-'0'] = true;
    }
    return res;
}

• encode не аллоцирует память, работает на массиве/строке фиксированной длины.
• Обратное преобразование (decode) потребуется лишь для восстановления пути, не для BFS.

2. Хранить всё в массивах фиксированного размера

cpp
std::array<int, 362880> dist;
std::array<int, 362880> parent;
std::array<char,362880> parent_move;

Нулевые инциализации memset-ом ≈ 3 МБ.

3. BFS без промежуточных карт

• В очереди лежат коды (int), а не строки.
• Для генерации соседей достаточно позиции «нуля» в строке (её можно хранить вместе с кодом или быстро искать по массиву).

4. Убрать неиспользуемое

Удаляем adj_, ind_state_, state_ind_, Gambit.

5. (Опционально) двусторонний BFS или A*

Даже односторонний BFS с числами проходит < 0.1 с, но если хочется ещё запас — запустите BFS одновременно от старта и цели.

---

Итог: скелет исправленного решения

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

constexpr int N = 362880;
constexpr int fact[10] = {1,1,2,6,24,120,720,5040,40320,362880};

int encode(const array<char,9>& s) { /* как выше */ }
array<char,9> decode(int code)      { /* обратная операция */ }

array<int,4> dx  = { -3, +3, +1, -1 };   // U, D, R, L
array<char,4> mv = { 'U','D','R','L' };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    array<char,9> start{};
    for (char &c : start) cin >> c;
    array<char,9> goal = {'1','2','3','4','5','6','7','8','0'};

    int sID = encode(start), gID = encode(goal);

    static int dist[N]; fill(begin(dist), end(dist), -1);
    static int par[N];  static char pMove[N];

    queue<int> q; q.push(sID); dist[sID] = 0;

    while (!q.empty()) {
        int v = q.front(); q.pop();
        if (v == gID) break;

        auto state = decode(v);
        int z = find(begin(state), end(state), '0') - begin(state);

        for (int k = 0; k < 4; ++k) {
            int nz = z + dx[k];
            if (nz < 0 || nz >= 9 || (z%3==0&&k==3) || (z%3==2&&k==2)) continue;

            swap(state[z], state[nz]);
            int to = encode(state);
            if (dist[to] == -1) {
                dist[to] = dist[v]+1;
                par[to]  = v;
                pMove[to]= mv[k];
                q.push(to);
            }
            swap(state[z], state[nz]);          // вернуть обратно
        }
    }

    if (dist[gID] == -1) { cout << -1; return 0; }

    string path;
    for (int cur = gID; cur != sID; cur = par[cur]) path += pMove[cur];
    reverse(path.begin(), path.end());

    cout << dist[gID] << '\n' << path << '\n';
}

- никаких unordered_map, ни одной аллокации во время работы – типичная реализация проходит < 0.05 с в g++-O2 и уверенно укладывается в лимит 2 с.

---

Главное, что «сломано» в исходном коде

Проблема	Почему медленно	Как исправить
Полный перебор next_permutation + две карты unordered_map<string, …>	Сотни тысяч хэширований и аллокаций строк	Кантор-кодирование → один int
Доступ к картам на каждом шаге BFS	Ещё сотни тысяч хэширований	Работаем только с int
Гигантский (и неиспользуемый) adj_	Лишняя инициализация 362 880 векторов	Удалить

Исправив эти места, программа легко проходит TL.