Noic - Semana 50 - Avançado - Problema 2

noic-s50-intermed-p2.cpp

// Noic - Semana 50 - Intermediário - Problema 2
// Complexidade: O(N * log_10 N)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 10010;

int dist[maxn];

bool mark[maxn];

vector<int> grafo[maxn];

// inverso de um número x qualquer
int inverso(int x)
{
    // guardaremos os dígitos de x neste vetor
    vector<int> digits;

    while (x > 0)
    {
        int d = x%10; // o último dígito de x é x%10
        x /= 10; // divimos x por 10 para encontrar os próximos dígitos

        digits.push_back(d);
    }

    // vamos percorrer os dígitos em ordem contrária
    reverse(digits.begin(), digits.end());

    int y = 0; // resposta

    for (int i = 0; i < digits.size(); i++)
    {
        // multiplicamos cada dígito pela sua respectiva potência de 10
        // (na ordem contrária de x)
        y += (pow(10, i)*digits[i]);
    }

    return y;
}

// menor distância de A para B
int bfs(int a, int b)
{
    queue<int> fila;
    fila.push(a);

    mark[a] = 1; // mark marca os vértices já visitados
    dist[a] = 0;

    while (!fila.empty())
    {
        int x = fila.front();
        fila.pop();

        for (auto v: grafo[x])
        {
            if (!mark[v])
            {
                dist[v] = dist[x]+1, mark[v] = 1;
                fila.push(v);
            }
        }
    }
    return dist[b]-dist[a];
}

int main(void)
{
    int a, b, t;
    scanf("%d", &t);

    while (t--)
    {
        int a, b;
        scanf("%d %d", &a, &b);

        for (int i = 1; i <= 10000; i++)
            grafo[i].clear();

        for (int i = 1; i <= 10000; i++)
        {
            // arestas do grafo
            grafo[i].push_back(i+1);
            grafo[i].push_back(inverso(i));
        }

        memset(mark, 0, sizeof mark);

        printf("%d\n", bfs(a, b));
    }
}