Реализация BFS с использованием очереди и списка смежности в C

Question

Я решал задачу, которая позволяла выполнять два типа операций: вычитать одно из числа или умножать его на два с указанием исходного и конечного номеров.Входные ограничения: 1 <= n <= 10 ^ 4 для обоих чисел.Я должен вывести количество операций, необходимых для получения желаемого числа из заданного.Следующее - моя реализация, получающая ошибку времени выполнения и, очевидно, я не знаю почему.Будет здорово, если кто-нибудь объяснит ошибку.Спасибо. </p>

#include <stdio.h>
#include <stdlib.h>
int g[22222][3], v[2222], size;//g == graph, v == visited and size == the size of queue
typedef struct _queue
{
    int val;
    struct _queue *next;
    struct _queue *prev;
} queue;
queue *head=NULL, *last=NULL;
void push(int val)
{
    queue *ptr=(queue *) malloc(sizeof(queue));
    ptr->next=NULL;
    ptr->val=val;
    if (head)
    {
        last->next=ptr;
        ptr->prev=last;
    }
    else
    {
        head=ptr;
        ptr->prev=NULL;
    }
    last=ptr;
}
void pop()
{
    if (size)
    {
        queue *ptr=last;
        last=last->prev;
        if (head) last->next=NULL;
        free(ptr);
    }
}
int front() {return last->val;}
int bfs(int s, int d)//s == source and d == destination
{
    int cnt=0;
    push(s);
    size++;
    v[s]=1;
    while (size)
    {
        int u=front();
        pop();
        size--;
        for (int j=1; j<=2; j++)
        {
            if (d==g[u][j]) return (cnt+1);
            if (!v[g[u][j]])
            {
                v[g[u][j]]=1;
                size++;
                push(g[u][j]);
            }
        }
        cnt++;
    }
}
int main()
{
    int n, m, val;
    scanf("%d%d", &n, &m);
    if (n==m) {printf("0"); return 0;}
    val=(n>m?n:m)*2;
    v[0]=1;
    for (int i=1; i<=val; i++)
    {
        g[i][1]=2*i;
        g[i][2]=i-1;
    }
    printf("%d", bfs(n, m));
    return 0;
}

Answer 1

Вы реализовали стек, то есть LIFO (последний пришел первым - вышел): вы добавляете в конец и извлекаете из конца.

Вы должны реализовать очередь, то есть FIFO (сначала в порядке очереди), поэтому, если вы добавите в конец, вы должны получить спереди:

void pop()
{
    if (size)
    {
        queue *ptr=head;
        head=head->next;
        if (head) head->prev=NULL;
        free(ptr);
    }
}
int front() 
{
   return head->val;
}

Кроме того, я думаю, ваша цель состоит в том, чтобыпосчитайте наименьшее количество операций, необходимых для получения желаемого числа из заданного.Ваша переменная cnt не представляет наименьшее количество операций, она представляет количество раз, которое вы извлекли элемент из очереди.Вам нужно увеличить его для каждого нового уровня .

Наконец, ваш bfs должен возвращать значение, даже если нет пути от s до d, поэтому вы должны поставить return 0; после цикла while(size){}.

UPD.Вам нужно пропустить g[u][j], если оно больше 2 * (10^4) внутри bfs, в противном случае эти значения будут помещены в очередь, что является пустой тратой пространства.Кстати, в вашем v массиве всего 2222 элемента, он должен содержать не менее 20001 (v[20000] - последний)