Ex2ED2

//-----------------------------------------

// EXERCICIO 2
// POR GABRIEL FERREIRA E VINICIUS SANTIAGO
// M 78218 e M 78208

//-----------------------------------------

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

int matriz[10][10];
int cAtual[11], cOriginal[11] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, }, cMenorCusto[11];
int n = 5, menorCusto;

void ler();

void imprimir(int vetor[11]);
void imprimirValorSoma(int soma);
void inverter(int inicio, int fim);
void copiar(int vetor1[11], int vetor2[11]);

void calcularHeuristica();
int calcularValor(int caminho[11]);
void validaCaminho(int caminho[11]);

int main() {
  srand(time(NULL));

  ler();

  calcularHeuristica();

  printf("\n\nMenor custo possivel: %d\n", menorCusto);
  printf("--------------------------------");
  imprimir(cMenorCusto);

  return 0;
}

int calcularValor(int caminho[11]) {
    int soma = 0, i;

    for(i = 0; i < n - 1; i++) {
        if(matriz[caminho[i]][caminho[i + 1]] != 0) {
            soma += matriz[caminho[i]][caminho[i + 1]];
            //printf("\nmatriz[%d][%d]: %d", caminho[i], caminho[i+1], matriz[caminho[i]][caminho[i + 1]]);
        } else {
            soma = 0;
            break;
        }

    }

    if(soma > 0) {
        if(matriz[caminho[i]][caminho[0]] != 0) {
            soma += matriz[caminho[i]][caminho[0]];
            if(soma < menorCusto) {
                menorCusto = soma;
                copiar(cMenorCusto, caminho);
            }
            //printf("\nmatriz[%d][%d]: %d", caminho[i], caminho[0], matriz[caminho[i]][caminho[0]]);
        } else {
            soma = 0;
        }
    }

    return soma;

}

void calcularHeuristica() {
    int j, i;
    for(j = 2; j < n; j++) {
        printf("\n\nFazendo troca entre %d\n", j);

        for(i = 1; i < n - j + 1; i++) {
            inverter(i, i + j - 1);
            imprimir(cAtual);
            imprimirValorSoma(calcularValor(cAtual));
        }
        getch();
    }
}

void imprimirValorSoma(int soma) {
    if(soma > 0) {
        printf(" = %d", soma);
    } else {
        printf(" = Alguma aresta eh vazia!");
    }
}

void inverter(int inicio, int qt) {
    int fim = inicio + qt + 1;
    int temp;

    copiar(cAtual, cOriginal);
    int contador;
    for (contador = inicio; contador < fim/2; ++contador){
        temp = cAtual[contador];
        cAtual[contador] = cAtual[fim - contador - 1];
        cAtual[fim - contador - 1] = temp;
   }
}

void copiar(int vetor1[11], int vetor2[11]) {
    int i;
    for(i = 0; i < n; i++) {
        vetor1[i] = vetor2[i];
    }
}

void imprimir(int vetor[11]) {
    printf("\n");
    int i;
    for(i = 0; i < n; i++) {
        printf("%d --> ", vetor[i]);
    }
    printf("%d", vetor[0]);
}

void imprimirMatriz() {
  int i, j;

  printf("\n     ");

  for(i = 0; i < n; i++) {
    printf("%2d ", i);
  }

  printf("\n-----");

  for(i = 0; i < n; i++) {
    printf("---");
  }

  printf("\n");

  for(i = 0; i < n; i++) {
    printf("%2d | ", i);
    for(j = 0; j < n; j++) {
        printf("%2d ", matriz[i][j]);
      }
      printf("\n");
  }
}

void ler() {
    int i, j;

    n = (rand() % 7) + 3;

    printf("Numero de nodos = %d\n", n);

    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            matriz[i][j] = rand() % 10;
        }
    }

    for(i = 0; i < n; i++) {
        matriz[i][i] = 0;
    }

    imprimirMatriz();

    do {

        cOriginal[0] = rand() % n;

        for(i = 0; i < n; i++) {
            int x = rand() % n;

            for(j = 0; j < i; j++) {
                if(cOriginal[j] == x) {
                    i--;
                    break;
                } else {
                    cOriginal[i] = x;
                }
            }
            //printf("\ncOriginal[%d] = %d", j, cOriginal[j]);
        }
    } while(calcularValor(cOriginal) == 0);

    imprimir(cOriginal);
    imprimirValorSoma(calcularValor(cOriginal));

    copiar(cMenorCusto, cOriginal);
    menorCusto = calcularValor(cOriginal);

}