Skip to content

Instantly share code, notes, and snippets.

@felipap
Created August 28, 2012 04:09
Show Gist options
  • Save felipap/3494890 to your computer and use it in GitHub Desktop.
Save felipap/3494890 to your computer and use it in GitHub Desktop.
#include <stdio.h>
#define CIDADES 20
int explorado[CIDADES],
localizacoes[CIDADES][CIDADES] =
{
{0, 71, -1, -1, -1, -1, -1, -1, -1, 151, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{71, 0, 75, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, 75, 0, 118, -1, -1, -1, -1, -1, 140, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, 118, 0, 111, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, 111, 0, 70, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, 70, 0, 75, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, 75, 0, 120, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, 120, 0, 146, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, 146, 0, 80, -1, 97, -1, -1, -1, -1, -1, -1, -1, -1},
{151, -1, 140, -1, -1, -1, -1, -1, 80, 0, 99, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, 99, 0, -1, 211, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, 97, -1, -1, 0, 101, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 211, 101, 0, -1, 85, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 85, -1, 0, 142, -1, -1, 98, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 142, 0, 92, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 92, 0, 87, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 87, 0, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 98, -1, -1, -1, 0, 86},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 86, 0},
};
int posicaoPonteiro (int vetor[]) {
int i;
for (i=0; i<CIDADES; i++)
if (vetor[i] == -1)
break;
printf("retornando ponteiro=%d\n", i);
return i;
}
void corrigevetor (int posAtual, int *lista) {
int i, j;
for (i=1; i<CIDADES; i++) {
j = i-1;
lista[j] = lista[i];
}
}
void conexoes (int posAtual, int *lista) {
int i=0, j;
for (j=0; j<CIDADES; j++) {
if (localizacoes[posAtual][j] > 0) {
if (explorado[j]) continue;
else
explorado[j] = 1;
i = posicaoPonteiro(lista);
lista[i] = j;
}
}
}
int buscaLargura (int posInicial, int posFinal) {
int j, fila[CIDADES], contador=0, i;
for (i=0; i<CIDADES; i++) {
fila[i] = -1;
explorado[i] = 0;
}
do {
printf("##################\ncontador = %d\n", contador);
conexoes(posInicial, fila);
for (i=0; i<CIDADES; i++) {
printf("fila[%d] = %d\n", i, fila[i]);
}
posInicial = fila[0];
corrigevetor(posInicial, fila);
printf("pos: %d\n", posInicial);
} while ((posInicial!=posFinal)
&& (++contador<12)
&& (posInicial!=-1));
puts("saiu");
return 1;
}
int main () {
int posInicial, posFinal;
printf("digite a localizacao inicial\n");
scanf("%d", &posInicial);
printf("digite a localizacao final\n");
scanf("%d", &posFinal);
printf("\n");
buscaLargura(posInicial, posFinal);
getch();
return 0;
}
@felipap
Copy link
Author

felipap commented Aug 28, 2012

include <stdio.h>

define CIDADES 20

int posicaoinicial, posicaofinal,
localizacoes[CIDADES][CIDADES] =
{
{0, 71, -1, -1, -1, -1, -1, -1, -1, 151, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{71, 0, 75, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, 75, 0, 118, -1, -1, -1, -1, -1, 140, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, 118, 0, 111, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, 111, 0, 70, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, 70, 0, 75, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, 75, 0, 120, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, 120, 0, 146, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, 146, 0, 80, -1, 97, -1, -1, -1, -1, -1, -1, -1, -1},
{151, -1, 140, -1, -1, -1, -1, -1, 80, 0, 99, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, 99, 0, -1, 211, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, 97, -1, -1, 0, 101, -1, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 211, 101, 0, -1, 85, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 85, -1, 0, 142, -1, -1, 98, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 142, 0, 92, -1, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 92, 0, 87, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 87, 0, -1, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 98, -1, -1, -1, 0, 86},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 86, 0},
};

int posicaovetor (int vetor[]) {
int i;
for (i=0; i<CIDADES; i++)
if (vetor[i]==-1)
break;
return i;
}

void corrigevetor (int posicaoatual, int *lista) {
int i, j;
for (i=1; i<CIDADES; i++){
j = i-1;
lista[j] = lista[i];
}
}

void conexoes (int posicaoatual, int *lista) {
int i=0, j;
for (j=1; j<CIDADES; j++) {
if (localizacoes[posicaoatual][j] > 0)
i = posicaovetor(lista);
lista[i] = j;
}
}

int buscaLargura (int posicaoInicial, int posicaoFinal) {
int j, lista[CIDADES], contador=0, i;

for (i=0; i<CIDADES; i++)
    lista[i] = -1;

do {
    conexoes(posicaoinicial, lista);
    for (i=0; i<CIDADES; i++)
        printf("lista[%d] = %d\n", i, lista[i]);
    corrigevetor(posicaoinicial, lista);
    posicaoinicial = lista[0];
    printf("%d\n", posicaoinicial);
    contador++;
    printf("contador = %d\n", contador);
} while ((posicaoinicial!=posicaofinal)
    && (contador<100)
    && (posicaoinicial!=-1));
return 1;

}

int main () {

printf("digite a localizacao inicial\n");
scanf("%d", &posicaoinicial);
printf("digite a localizacao final\n");
scanf("%d", &posicaofinal);
printf("\n");
buscaLargura(posicaoinicial, posicaofinal);

getch();
return 0;

}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment