Bunich

Cammino massimo matrice

Feb 12th, 2018
88
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <limits.h>
  4.  
  5. typedef struct sol{
  6.     int n;
  7.     int s;
  8. }Sol;
  9.  
  10. void maxPath(int nr, int nc, int *val);
  11. void mpathR(int pos, int start, int fst, int fend, int *val, int *sol, int dim, Sol *ssol, int iprec, int nc, int nr);
  12.  
  13. int main()
  14. {
  15.     int val[9]={1,2,-3,9,-9,7,0,1,4};
  16.     maxPath(3,3,val);
  17.     return 0;
  18. }
  19.  
  20. void maxPath(int nr, int nc, int *val){
  21.     int i, *sol;
  22.     Sol s;
  23.     s.n=0;s.s=INT_MIN;
  24.     sol=(int*)malloc((nr*nc)*sizeof(int));
  25.     for(i=1;i<nr*nc; i++){
  26.         mpathR(0,0,0,0,val,sol,i,&s,0,nc,nr);
  27.     }
  28.  
  29.     printf("Best sol: %d \nPassi:%d\n",s.s,s.n);
  30.     return;
  31. }
  32.  
  33. void mpathR(int pos, int start, int fst, int fend, int *val, int *sol, int dim, Sol *ssol, int iprec, int nc, int nr){
  34.     int i,s=0,contr=0;
  35.  
  36.     if(pos>=dim){
  37.  
  38.         for(i=0;i<dim;i++)
  39.             s+=sol[i];
  40.         if(s>ssol->s && fst && fend){
  41.             ssol->s=s;
  42.             ssol->n=dim;
  43.         }
  44.         return;
  45.     }
  46.  
  47.     for(i=start;i<(nr*nc);i++){
  48.         contr=abs(iprec/nc-i/nc)+abs(iprec%nc-i%nc);
  49.         if(contr<=2){
  50.             if(i/nc==0 && i%nc==0)
  51.                 fst=1;
  52.             if(i/nc==nr-1 && i%nc==nc-1)
  53.                 fend=1;
  54.             sol[pos]=val[i];
  55.             mpathR(pos+1,i+1,fst,fend,val,sol,dim,ssol,i,nc,nr);
  56.         }
  57.     }
  58.     return;
  59. }
RAW Paste Data