uri-1550.cpp

#include <bits/stdc++.h>

#define MAXN 10000009
typedef long long int ll;
using namespace std;

// Função utilitária para inverter um número
int reverse(int n) {
  int reversedNumber = 0, remainder;
  while(n != 0) {
    remainder = n % 10;
    reversedNumber = reversedNumber * 10 + remainder;
    n /= 10;
  }
  
  return reversedNumber;
}

// Função simples que apenas adiciona uma unidade a um número
int add(int n) {
    return n + 1;
}

/*
  Vetor que será reutilizado para armazenar os vizinhos de um nó,
  todo nó terá no máximo dois vizinhos
*/
int neighbors[2];

/*
  Função que resolverá o problema é uma simples busca em largura,
  Na teoria dos grafos, busca em largura é 
  um algoritmo de busca em grafos utilizado para realizar uma busca ou 
  travessia num grafo e estrutura de dados do tipo árvore
*/
int bfs(int a, int b) {
    // Mapa que armazenará as distâncias
    map<int, int> dist;
    // Fila usada para armazenar os nós visitados
    queue<int> q;
    
    // Inicializa a primeira posição do mapa com valor 0;
    dist[a] = 0;
    // Adiciona o valor inicial da tela a fila
    q.push(a);
    
    // Enquanto a fila não estiver vazia:
    while(!q.empty()) {
        // Pega o elemento da frente da fila
        int current = q.front();
        // Remove o elemento da frente da fila
        q.pop();
        // Caso o elemento seja igual ao valor buscado, finaliza o laço
        if (current == b) break;
        /*
          Existem duas possibilidades no visor:
          Botão 1 - Incrementa o valor atual
          Botão 2 - Inverte o número atual
        */
        neighbors[0] = add(current);
        neighbors[1] = reverse(current);
        
        // Mapeamos os vizinhos do nó atual
        for (int neighbor: neighbors) {
            /*
              Para evitar o recálculo, caso o item já tenha sido calculado, simplesmente
              ignoramos o nó atual
            */
            if (!dist.count(neighbor)) {
                dist[neighbor] = add(dist[current]);
                q.push(neighbor);
            } 
        }
    }
    
    
    /*
      No fim, obtemos o mapa completo com as distância e retornamos a chave referente
      ao destino
    */
    return dist[b];
}

int main() {
    int n, a, b;
    
    cin >> n;
    
    while (n--) {
      cin >> a >> b;
      cout << bfs(a, b) << "\n";
    }
    
	return 0;
}