Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2331
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2331
Uiquipédia
Por OBI - Olimpíada Brasileira de Informática 2007 
Brazil
Timelimit: 1
A Uiquipédia (Wikipedia em inglês), fundada em 2001 por Jimmy Wales e Larry Sanger, é um site onde qualquer pessoa pode editar os artigos, fazendo correções ou ampliando seu conteúdo.
Uma das grandes vantagens da Uiquipédia sobre enciclopédias de papel é a facilidade de seguir referências; com um simples clique, é possível ir de um artigo para outro relacionado. Essas referências são chamadas de referências diretas. Também é possível navegar a Uiquipédia sequencialmente: cada artigo possui referência para o artigo anterior e para o posterior, na ordem alfabética. Essas referências são chamadas de referências sequenciais.
Por exemplo, um artigo para o termo "Elefante" pode ter uma referencia direta para "Mamiferos" em seu texto, desta forma pode-se chegar de "Elefante" a "Mamiferos" em um clique. Observe que pode não existir a referência direta contrária, ou seja, de "Mamiferos" para "Elefante". Adicionalmente se "Elevador" é o próximo artigo depois de "Elefante", na ordem alfabética, pode-se ir com um clique de "Elefante" para "Elevador" e de "Elevador" para "Elefante", pois há uma referência sequencial entre eles.
Paulo e André são dois amigos que contribuem para a Uiquipédia. Muitas vezes, André edita um artigo e quer que Paulo o ajude a revisar a modificação. A conexão de Paulo à Internet é discada, e por isso ele quer chegar na página que André editou usando o menor número de cliques possível, começando do artigo em que está, e navegando apenas por referências, diretas ou sequenciais.
Escreva um programa que, dados todas as referências diretas existentes na Uiquipédia, a página onde Paulo está, e a página editada por André, determina de quantos cliques Paulo precisa, no mínimo, para ver a página que foi modificada por André, utilizando as referências diretas e sequenciais.
Entrada
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha contém um único inteiro, N , que é o número de referências da Uiquipédia (1 ≤ N ≤ 1.000). As N linhas contém cada uma duas strings X e Y , separadas por um espaço, que são os nomes de duas páginas da Uiquipédia conectadas por uma referência direta (de X para Y ). Todo artigo existente na Uiquipédia aparece pelo menos uma vez na descrição das referencias diretas, permitindo que as referencias sequenciais sejam extraídas das informações dadas. Note que uma referência direta pode ligar duas páginas que estariam ligadas também por uma referência sequencial.
Depois da descrição das referências, há uma linha em branco, e a linha seguinte contém duas cadeias de caracteres, P e A, que são a página atual de Paulo e a página editada por André. O nome de cada página é limitado a 100 caracteres e contém somente letras maiúsculas, letras minusculas e o símbolo '_'. Observe que na ordem alfabética o simbolo '_' é anterior às letras maiúsculas, que por sua vez são anteriores às letras minusculas
Saída
Seu programa deve imprimir, na saída padrão, uma única linha, contendo um único inteiro, que diz o número mínimo de cliques que são necessários para ir da página atual de Paulo até a página editada por André. Sempre é possível navegar de um artigo a outro.
| Exemplos de Entrada | Exemplos de Saída |
|
3 Pink_Floyd O_Lado_Escuro_Da_Lua Pink_Floyd O_Muro O_Muro Muro_de_Berlim O_Muro O_Lado_Escuro_Da_Lua |
1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define MP make_pair
#define PB push_back
#define MAXN 10000
using namespace std;
typedef pair < int, int> ii;
typedef map::iterator ssit;
vector<int> grafo[MAXN], lista;
map < string, int> mapa;
bool visitado[MAXN];
int resposta, n, contador, ini, fim;
string inicio, final;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
string nome1, nome2;
cin >> nome1 >> nome2;
if (mapa.find(nome1) == mapa.end()) {
mapa[nome1] = ++contador;
}
if (mapa.find(nome2) == mapa.end()) {
mapa[nome2] = ++contador;
}
int codigo1 = mapa[nome1], codigo2 = mapa[nome2];
grafo[codigo1].PB(codigo2);
}
for (ssit pcomeco = mapa.begin(); pcomeco != mapa.end(); pcomeco++) {
lista.PB((*pcomeco).second);
}
for (int i = 0; i < (lista.size()) - 1; i++) {
int h = lista[i], g = lista[i + 1];
grafo[h].PB(g);
grafo[g].PB(h);
}
cin >> inicio >> final;
ini = mapa[inicio];
fim = mapa[final];
queue < ii> bfs;
bfs.push(MP(ini, 0));
while (!bfs.empty()) {
ii agora = bfs.front();
bfs.pop();
int vertice = agora.first, percorrido = agora.second;
if (vertice == fim) {
cout << percorrido << endl;
return 0;
}
if (visitado[vertice]) continue;
visitado[vertice] = true;
for (int i = 0; i < (int)grafo[vertice].size(); i++)
bfs.push(MP(grafo[vertice][i], percorrido + 1));
}
return 0;
}
Input
Pink_Floyd O_Lado_Escuro_Da_Lua
Pink_Floyd O_Muro
O_Muro Muro_de_Berlim
O_Muro O_Lado_Escuro_Da_Lua
Output