Advertisement
pmanriquez93

Unidirectional TSP - A medias

Jun 22nd, 2014
557
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.95 KB | None | 0 0
  1. /*
  2.  * File:   main.c
  3.  * Author: Pablo
  4.  *
  5.  * Created on 22 de junio de 2014, 08:46 PM
  6.  */
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <limits.h>
  11. #define MAX_FIL 11
  12. #define MAX_COL 100
  13.  
  14. void imprimirArreglo(int DP[MAX_FIL][MAX_COL], int fil, int col){
  15.     int i,j;
  16.     for (i=0;i<fil;i++){
  17.             for(j=0;j<col;j++)
  18.                 printf("%4d",DP[i][j]);
  19.             printf("\n");
  20.     }
  21.    
  22.    
  23. }
  24.  
  25. int minimo(int a, int b, int c){
  26.     if (a<b){
  27.         if (a<c)
  28.             return a;
  29.         else
  30.             return c;
  31.     }else{
  32.         if(b<c)
  33.             return b;
  34.         else
  35.             return c;
  36.     }
  37. }
  38.  
  39. void inicializarTabla(int DP[MAX_FIL][MAX_COL], int fil, int col){
  40.     int i,j;
  41.     for (i=0;i<fil;i++)
  42.             for(j=0;j<col;j++)
  43.                 DP[i][j]=INT_MAX;
  44.    
  45. }
  46.  
  47. void llenarTabla(int DP[MAX_FIL][MAX_COL],int A[MAX_FIL][MAX_COL],
  48.                 int fil, int col){
  49.     int a,i,j;
  50.     for (a=0;a<fil;a++)
  51.         DP[a][0]= A[a][0];
  52.  
  53.     for (j=1;j<col;j++)
  54.             for(i=0;i<fil;i++){
  55.                 if (i==0){
  56.                     DP[i][j] = A[i][j] +
  57.                                minimo(DP[0][j-1],DP[fil-1][j-1],DP[1][j-1]);                                        
  58.                 }
  59.                 else if(i==fil-1){
  60.                     DP[i][j] = A[i][j] +
  61.                                minimo(DP[fil-1][j-1],DP[fil-2][j-1],DP[0][j-1]);
  62.                                        
  63.                 }
  64.                 else{
  65.                     DP[i][j] = A[i][j] +
  66.                                minimo(DP[i][j-1],DP[i+1][j-1],DP[i-1][j-1]);  
  67.                 }      
  68.             }                
  69. }
  70.  
  71. int mejorCamino(int DP[MAX_FIL][MAX_COL],int fil,int col){
  72.     int i,min;
  73.     min = INT_MAX;
  74.     for(i=0;i<fil;i++){
  75.         if (DP[i][col-1]< min)
  76.             min = DP[i][col-1];
  77.     }
  78.     return min;
  79. }
  80.  
  81. void hallarFilas(int resultados[MAX_COL],int DP[MAX_FIL][MAX_COL],
  82.                 int fil, int col){
  83.     int a,min,filAux,colAux;
  84.     min = INT_MAX;
  85.     for(a=0;a<fil;a++){
  86.         if (DP[a][col-1]< min){
  87.             min = DP[a][col-1];
  88.             filAux = a;
  89.             colAux = col-1;
  90.         }  
  91.     }
  92.     int i,j;
  93.     for (i=colAux;i>=0;i--){
  94.        
  95.     }
  96.    
  97.    
  98.    
  99. }
  100.  
  101. int main(int argc, char** argv) {
  102.     int fil,col,max;
  103.     int A[MAX_FIL][MAX_COL];
  104.     int DP[MAX_FIL][MAX_COL];
  105.     int resultados[MAX_COL];
  106.    
  107.     while(scanf("%d %d",&fil,&col)!= EOF){
  108.         int i,j,rpta;
  109.         for (i=0;i<fil;i++)
  110.             for(j=0;j<col;j++)
  111.                 scanf(" %d",&A[i][j]);
  112.        
  113.         inicializarTabla(DP,i,j);
  114.         llenarTabla(DP,A,fil,col);
  115.         /*printf("\n");
  116.         imprimirArreglo(A,i,j);
  117.         printf("\n");
  118.         imprimirArreglo(DP,fil,col);*/
  119.         rpta = mejorCamino(DP,fil,col);
  120.         printf("%d",rpta);
  121.         hallarFilas(resultados,DP,fil,col);
  122.     }
  123.    
  124.  
  125.     return (EXIT_SUCCESS);
  126. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement