Guilherme97

Olá, estou fazendo uma lista de exercicios e me deparei com este: UIQUIPÉDIA (OBI 2007) 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 Ui-quipédia sequencialmente: cada artigo possui referência para o artigo anterior e para o pos-terior, 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 “Mamí-feros” em seu texto, desta forma pode-se chegar de “Elefante” a “Mamíferos” em um clique. Observe que pode não existir a referência direta contrária, ou seja, de “Mamíferos” 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 “Ele-fante”, pois há uma referencia sequencial entre eles. Paulo e André são dois amigos que contribuem para a Uiquipédia. Muitas vezes, André edi-ta um artigo e quer que Paulo o ajude a revisar a modificação. A conexão de Paulo à Inter-net é 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 refe-rencias, diretas ou sequenciais. Tarefa 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ên-cias 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úme-ro 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 conec-tadas 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 referências 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ús-culas, letras minúsculas e o símbolo ’-’. Observe que na ordem alfabética o símbolo ’-’ é anterior às letras maiúsculas, que por sua vez são anteriores às letras minúsculas. 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. Nas imagens, é possível ver o que se pede no exercicio, quantidade de clicks para chegar de uma pagina a outra, dando todos os link possiveis. Como fazer esse programa? isso é o que eu fiz até agora, li os links e salvei em uma matriz de caracteres. Mas como devo tratar os dados para que eu consiga testar todos os caminhos e ver qual tem menos clicks? me deem dicas, please #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h> int thesame(char* str1,char* str2){ int i; for(i=0;(str1[i]!='\0')&&(str2[i]!='\0');i++){ if(str1[i]!=str2[i]){ return 0; } } if(str1[i]==str2[i]){ return 1; }else{ return 0; } } int main(){ int n,i,j,k; char ***ref,input[201],final[2][100]; scanf("%d",&n); ref=(char***)malloc(n*sizeof(char**)); for(i=0;i<n;i++) { ref[i]=(char**)malloc(2*sizeof(char*)); ref[i][0]=(char*)malloc(100*sizeof(char)); ref[i][1]=(char*)malloc(100*sizeof(char)); fflush(stdin); gets(input); k=0; for(j=0;input[j]!=' ';j++) { ref[i][0][k]=input[j]; k++; } ref[i][0][k]='\0'; k=0; for(j+=1;input[j]!='\0';j++) { ref[i][1][k]=input[j]; k++; } ref[i][1][k]='\0'; }// free variables: i,j,k fflush(stdin); gets(input); fflush(stdin); gets(input); k=0; for(j=0;input[j]!=' ';j++) { final[0][k]=input[j]; k++; } final[0][k]='\0'; k=0; for(j+=1;input[j]!='\0';j++) { final[1][k]=input[j]; k++; } final[1][k]='\0'; printf("\n\n"); printf("%s --> %s\n",final[0],final[1]); printf("\n\n"); for(i=0;i<n;i++) { printf("%s --> %s\n",ref[i][0],ref[i][1]); } printf("\n\n"); //show all references }