@impelix

А как предков вывести?

Ну и трудный день конечно сегодня, чувствую весь тес с++ в моих вопросах, но таков путь(кому интересно с конем справился)
ну так вот есть задача.
Витя хочет придумать новую игру с числами. В этой игре от игроков требуется преобразовывать четырехзначные числа не содержащие нулей при помощи следующего разрешенного набора действий:

1. Можно увеличить первую цифру числа на 1, если она не равна 9.

2. Можно уменьшить последнюю цифру на 1, если она не равна 1.

3. Можно циклически сдвинуть все цифры на одну вправо.

4. Можно циклически сдвинуть все цифры на одну влево.

Входные данные:
Во входном файле содержится два различных четырехзначных числа, каждое из которых не содержит нулей.
Выходные:
Программа должна вывести последовательность четырехзначных чисел, не содержащих нулей. Последовательность должна начинаться первым из данных чисел и заканчиваться вторым из данных чисел, каждое последующее число в последовательности должно быть получено из предыдущего числа применением одного из правил. Количество чисел в последовательности должно быть минимально возможным

И код вроде правильный, а вывод не выходит. Просто нету. ЗНаю что вывод долгий
Ну и сам код собственно говоря
#include <bits/stdc++.h>

using namespace std;
int sk;
vector<int> xcor;
vector<int> ycor;
int f1(int num){
    if (num / 1000 != 9){
        return num + 1000;
    }
    else return num;
}
int f2(int num){
    if(num % 10 != 1){
        return num - 1;
    }
    return num;
}
int f3(int num){
    int sum = 0;
    sum += 1000 * (num % 10);
    sum +=100 * (num / 1000);
    sum += 10 * ((num % 1000) / 100);
    sum += num % 10;
    return sum;
}
int f4(int num){
    int sum = 0;
    sum += ((num % 1000) / 100);
    sum += ((num % 100) / 10);
    sum += 10 * (num % 10);
    sum += num / 1000;
    return sum;
};




struct ch
{
    int num, dist, pred;
    ch(int num, int dist = 0, int pred = 0) : num(num), dist(dist), pred(pred){}
};
vector<ch> ans;
int BFS(ch st)
{
    queue<ch> q;
    q.push(st);
    while (!q.empty())
    {
        ch node = q.front();
        q.pop();
        int newnum = 0;
        int num = node.num;
        int dist = node.dist;
        if (num == sk)
            return dist;
        else{
            newnum = f1(num);
            if (newnum != sk) {
                q.push({newnum, dist + 1, num});
                ans.push_back({newnum, dist + 1, num});
            }
            else{
                return dist + 1;
            }
            newnum = f2(num);
            if (newnum != sk) {
                q.push({newnum, dist + 1, num});
                ans.push_back({newnum, dist + 1, num});
            }
            else{
                return dist + 1;
            }
            newnum = f3(num);
            if (newnum != sk) {
                q.push({newnum, dist + 1, num});
                ans.push_back({newnum, dist + 1, num});
            }
            else{
                return dist + 1;
            }
            newnum = f4(num);
            if (newnum != sk) {
                q.push({newnum, dist + 1, num});
                ans.push_back({newnum, dist + 1, num});
            }
            else{
                return dist + 1;
            }
        }
    }
    return 10000;
}
void vyvod(int num){
    if (num == 0){
        return;
    }
    for (int i = 0; i < ans.size(); ++i){
        if(ans[i].pred == num){
            vyvod(ans[i].pred);
            cout << num;
        }
    }

}


int main()
{
    int num;
    cin >> num >> sk;
    ch start = {num, 0, 0 };
    cout<<BFS(start) - 2;
    vyvod(sk);
    return 0;
}

По переменным ск то что ищем, num начальное число, pred-предок числа
  • Вопрос задан
  • 203 просмотра
Пригласить эксперта
Ответы на вопрос 2
Alexandroppolus
@Alexandroppolus
кодир
здесь никакой bfs не нужен.

Стартовое число в итоге будет повернуто на 0, 1, 2 или 3 вправо (это разница поворотов вправо и влево). То есть возможны 4 стратегии. Тебе надо сравнить 4 различных сдвигов исходного числа, посчитав для каждого сдвига суммарную стоимость преобразований.

например,
A = 2573
B = 4164

нулевой сдвиг дает стоимость действий 1 и 2: (4-2) + (5-1) + (7-6) + (4-3) = 2 + 4 + 1 + 1 = 8, плюс ещё надо здесь прикинуть оптимальную стратегию разворотов и посчитать, сколько их будет.

сдвиг на 1 вправо (стартовое число 3257) по действиям 1 и 2 выходит (4-3) + (2-1) + (6-5) + (7-4) = 6, и снова надо прикинуть развороты.

определив таким образом оптимальную - самую дешевую - стратегию (т.е. определив, насколько в итоге будет повернуто исходное число), выстраиваешь цепочку переходов.
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Опять у вас обход вширину написан через одно место.

В очередь вы должны класть только идентификатор вершины/состояния. В той задаче это были 2 координаты клетки поля. Тут - это четырехзначное число.

Найденное расстояние, путь к предку, пометка о посещении - все это не кладется в очередь, а лежит отдельно от него в массиве. В некоторых задачах, когда граф огромен (и неявно задан - вроде бесконечного шахматного поля), то нужно завести ассоциативный массив (мап), который хранил бы расстояние/предка/пометку только для посещенных вершин. Тут же меньше 10000 вершин всегда, поэтому тупо заведите массив на 10000 элементов и не мучайтесь.

Еще раз, в очереди у вас только число, а в массиве рядом пометки о песещении и путь к предку (расстояние конкретно в этой задаче считать и выводить не нужно).

Взяли из очереди 4-х значное число, произвели над ним 4 возможные операции, получили 4 новых числа. В массиве посмотрели что новое число не было обработано, тогда кладем его в очередь, помечаем обработанным и запоминаем, что для нового числа предок - текущее.

В конце надо циклом while от конечной вершины по сохраненным предкам идти, пока не упретесь в начало. Потом список обойденных чисел надо развернуть. Или хитрость - проводите обратные операции начиная с конечного состояния, пока не найдете начальное. Операции развернуть просто - вычитайте из первой цифры и прибавляйте к последней. Сдвиги симметричны и остаются как есть. Тогда не надо разворачивать ответ после восстановления циклом while.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы