Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // 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));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement