Solução por Rogério Júnior
O leitor atento consegue notar facilmente que este é um problema de grafos. Basta vermos cada página como um vértice do grafo, assim, vamos ligar duas página com uma aresta apenas se for possível ir de uma até a outra com um único clique. Se você nunca ouviu falar de grafos, clique aqui para ver a aula introdutória de grafos do Curso Noic. Feita essa análise, é fácil notar que encontrar o menor número de cliques que precisamos para ir de uma página até a outra é o mesmo que encontrar o comprimento do menor caminho que liga duas páginas. Se você nunca resolveu um problema assim, clique aqui para ver a aula do Curso Noic sobre menor caminho em um grafo.No grafo construído, todas as arestas têm peso 1, pois não existe um tipo de clique que custe mais que outro. Logo, como dito na aula, podemos simplesmente usar uma BFS para descobrir o menor caminho entre duas páginas. Se você não conhece esse algoritmo, clique aqui para ver a aula de Flood Fill do Curso Noic.
Assim, basta criarmos um grafo com todos os vértices (páginas) e arestas descritas na entrada (links entre páginas). Feito isso, vamos adicionar também as arestas entre páginas adjacentes na ordem alfabética de todas as páginas da Uiquipédia, pois também é possível acessar páginas vizinhas com um único clique. Para implementarmos tal grafo, é necessária uma estrutura de dados onde possamos salvar frases (string de C++) e acessá-las rapidamente, visto que usaremos uma matriz de adjacência para representarmos o grafo. Desse modo, cada vértice será identificado por um inteiro de 1 até counter (o número de páginas), e precisamos saber, de maneira rápida, qual o número de identificação de uma página apenas pelo seu nome. Para isso, usaremos uma map de nome mapa, onde as chaves serão strings (os nomes das páginas) e os elementos serão inteiros (seus números de identificação). A lista de adjacência será feita com uma matriz de bool, MAXN por MAXN (onde MAXN é número máximo de páginas), de nome tab. Nesse caso, tab[v][u] é true se existe uma aresta que liga o vértice v ao vértice u, ou false, caso contrário. Se você não conhece essas estruturas, clique aqui para ver a aula do Curso Noic sobre estruturas do C++.
Desse modo, vamos ler o valor de n, número de links da Uiquipédia, e usaremos um for para, em cada um desses links, declararmos e lermos duas strings: page1 e page2, nessa ordem, com o comando "cin >> page1 >> page2;". Feito isso, vamos checar se a página page1 já existe no grafo. Para isso, chamaremos um membro de mapa, a função find(page1), que retornará um ponteiro para a posição page1 de mapa, se ela existir, ou para mapa.end(), caso contrário. Se a página não existir, devemos criá-la, adicionando um ao valor de counter e salvando que o número da página page1 é counter, com o comando: "if(mapa.find(page1)==mapa.end()) mapa[page1]=++counter;". Repetiremos o mesmo processo com a segunda página. Agora, precisaremos adicionar a aresta que liga page1 a page2 (nessa ordem) ao grafo, através do comando "tab[mapa[page1]][mapa[paage2]]=true;".
Depois que lemos a entrada, precisamos adicionar as arestas que ligam páginas vizinhas. Como o map guarda seus elementos em ordem crescente de chave, as páginas estarão salvas em ordem alfabética. Desse modo, basta criarmos dois iterators, it e at que representarão uma págian e sua antecessora. Eles começarão com o valor de mapa.begin() e depois usarei o comando it++ para que este se torne um ponteiro para a segunda página. Com um for faremos it percorrer todas as posições de mapa, e ligaremos os vértices salvos em (*it).second e (*at).second com duas arestas, uma que parte do elemento em at e outra que parte do elemento em it. Ao final de cada repetição do for, faço at receber o valor de it, para que ele se torne um ponteiro para o antecessor da próxima página.
Agora, o grafo já está pronto, e basta que eu leia a página de origem e a de destino e imprima a distância entre elas que será calculada com uma BFS. Para isso, basta que salvemos a distância de cada vértice até a origem no vetor dist, que começará com todos os valores iguais a infinito, exceto o da posição da origem, que será zero. Assim, toda vez que formos adicionar um vértice à fila da BFS, salvamos que sua distância à origem é a distância de seu pai somada de 1, e retornarmos a distância até o destino. Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <map> | |
| #include <queue> | |
| #include <string> | |
| #include <iostream> | |
| using namespace std; | |
| #define MAXN 2020 | |
| #define INF 999999999 | |
| int n, counter; | |
| bool tab[MAXN][MAXN]; // grafo | |
| int dist[MAXN]; // array para a bfs | |
| map<string, int> mapa; // guarda o número de identificação de cada página | |
| // função bfs, que recebe as páginas de origem e destino como parâmetros | |
| int bfs(int ori, int dest){ | |
| // infinito as distâncias à ori, e faço com que a distância de ori a ori seja zero | |
| for(int i=1; i<=counter; i++) dist[i]=INF; dist[ori]=0; | |
| // declaro a fila da BFS e coloco nela o vértice ori | |
| queue<int> fila; fila.push(ori); | |
| // enquanto a pilha não estiver vazia | |
| while(!fila.empty()){ | |
| // v será o primeiro vértice na fila | |
| int v=fila.front(); fila.pop(); // e retiro o vértice da frente | |
| // para cada um dos vértices do grafo | |
| for(int u=0; u<=counter; u++){ | |
| // se existe uma aresta entre ele e v, e ele ainda não foi marcado | |
| if(tab[v][u] and dist[u]==INF){ | |
| // salvo que sua distância à ori é a distância de v somada de 1 | |
| dist[u]=dist[v]+1; | |
| fila.push(u); // e o adiciono à fila da BFS | |
| } | |
| } | |
| } | |
| // no fim, a função retorna a distância de dest até a origem | |
| return dist[dest]; | |
| } | |
| int main(){ | |
| cin >> n; // leio o número de links | |
| for(int i=1; i<=n; i++){ // para cada link | |
| // declaro e leio as páginas linkadas por ele | |
| string page1, page2; | |
| cin >> page1 >> page2; | |
| // adiciono ao grafo as páginas que ainda não existem nele | |
| if(mapa.find(page1)==mapa.end()) mapa[page1]=++counter; | |
| if(mapa.find(page2)==mapa.end()) mapa[page2]=++counter; | |
| // e represento o link entre page1 e page2 com uma aresta direcionada no grafo | |
| tab[mapa[page1]][mapa[page2]]=true; | |
| } | |
| // declaro os iteradores it e at apontando para o começo de mapa | |
| map<string,int>::iterator it=mapa.begin(), at=mapa.begin(); | |
| it++; // e faço it reeceber o próximo elemento de mapa | |
| for(; it!=mapa.end(); it++){ // percorro mapa com it | |
| // e crio uma aresta bidirecional entre páginas vizinhas | |
| tab[(*it).second][(*at).second]=tab[(*at).second][(*it).second]=true; | |
| at=it; // e faço at receber o próximo elemento de mapa | |
| } | |
| // declaro e leio as páginas de origem e destino da busca | |
| string page_ori, page_dest; | |
| cin >> page_ori >> page_dest; | |
| // e imprimo a distância entre elas através de uma BFS, seguida da quebra de linha | |
| cout << bfs(mapa[page_ori], mapa[page_dest]) << endl; | |
| return 0; | |
| } |