Bunich

tutto esame 12_matrice cammino massimo

Feb 11th, 2018
106
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. #define R 3
  6. #define C 3
  7.  
  8. struct node{
  9.     struct node *l;
  10.     struct node *r;
  11.     char k;
  12. };
  13.  
  14. int matPath(int **val, int **sol);
  15. void matSolR(int r, int c, int **sol, int **val, int *bSol);
  16. void matPathR(int r, int c, int path,int count,int **val, int** sol, int *bPath, int *bCount, int** mark);
  17. void alfiere(int *r, int *c, int **m, int row, int col);
  18. int sommaDiag(int r, int c, int** m, int row, int col);
  19. int KEYcmp(char c1, char c2);
  20. struct node *leggiAlb(char *file);
  21. struct node *NEW(char k);
  22. struct node *albreadR(FILE *fp);
  23. char *strdup(const char*);
  24. int TREEisomorph(struct node *t1, struct node *t2);
  25. int main()
  26. {
  27.  
  28.     int bSol=INT_MIN, **sol, i;
  29.     int **val;
  30.     sol=malloc(R*sizeof(int*));
  31.     val=malloc(R*sizeof(int*));
  32.     for(i=0;i<R;i++){
  33.         sol[i]=malloc(C*sizeof(int));
  34.         val[i]=malloc(C*sizeof(int));
  35.     }
  36.     val[0][0]=1;val[0][1]=2;val[0][2]=-3;
  37.     val[1][0]=9;val[1][1]=-9;val[1][2]=7;
  38.     val[2][0]=0;val[2][1]=1;val[2][2]=4;
  39.  
  40.     matSolR(0,0,sol,val,&bSol);
  41.     printf("Cammino massimo: %d\n",bSol);
  42.  
  43.     /*
  44.     int r=0,c=0,**val,i;
  45.     val=malloc(4*sizeof(int*));
  46.     for(i=0;i<4;i++){
  47.         val[i]=malloc(4*sizeof(int));
  48.     }
  49.     val[0][0]=0;val[0][1]=3;val[0][2]=4;val[0][3]=0;
  50.     val[1][0]=1;val[1][1]=0;val[1][2]=6;val[1][3]=6;
  51.     val[2][0]=1;val[2][1]=3;val[2][2]=9;val[2][3]=0;
  52.     val[3][0]=0;val[3][1]=0;val[3][2]=3;val[3][3]=1;
  53.     alfiere(&r,&c,val,4,4);
  54.     printf("pos: r=%d c=%d\n",r+1,c+1);
  55.     */
  56.     /*
  57.     struct node *h1;
  58.     struct node *h2;
  59.     int n;
  60.     h1=leggiAlb("alb.txt");
  61.     h2=leggiAlb("alb2.txt");
  62.     n=TREEisomorph(h1,h2);
  63.     printf("res: %d\n",n);
  64.  
  65.     */
  66.     return 0;
  67. }
  68.  
  69. void matSolR(int r, int c, int **sol, int **val, int *bSol){
  70.     int n,i;
  71.  
  72.     if(c==C){
  73.         c=0;
  74.         r++;
  75.     }
  76.  
  77.     if(r>=R){/*
  78.         for(i=0;i<R;i++){
  79.             for(j=0;j<C;j++){
  80.                 printf("%d ",sol[i][j]);
  81.             }
  82.             printf("\n");
  83.         }
  84.         printf("\n");*/
  85.  
  86.         n=matPath(val,sol);
  87.         if(n>*bSol)
  88.             *bSol=n;
  89.         return;
  90.     }
  91.  
  92.     for(i=0;i<2;i++){
  93.         sol[r][c]=i;
  94.         matSolR(r,c+1,sol,val,bSol);
  95.     }
  96.     return;
  97. }
  98.  
  99. int matPath(int **val, int **sol){
  100.     int bPath=INT_MIN, r=0, c=0, bCount=INT_MAX;
  101.     int **mark, i;
  102.     mark=(int**)malloc(R*sizeof(int*));
  103.     for(i=0;i<R;i++)
  104.         mark[i]=(int*)calloc(C,sizeof(int));
  105.  
  106.     matPathR(r,c,0,0,val,sol,&bPath,&bCount, mark);
  107.     return bPath;
  108. }
  109.  
  110. void matPathR(int r, int c, int path,int count,int **val, int** sol, int *bPath, int *bCount, int** mark){
  111.  
  112.     if(sol[r][c]==0 || r<0 || c<0 || r>=R || c>=C)return;
  113.  
  114.     if(r==R-1 && c==C-1){
  115.         if(sol[r][c])
  116.             path+=val[r][c];
  117.  
  118.         if(path>*bPath){
  119.             *bPath=path;
  120.             *bCount=count;
  121.             //printf("Passi: %d\n",count);
  122.         }
  123.         if(path==*bPath && count<*bCount){
  124.             *bCount=count;
  125.             //printf("Passi_m: %d\n",count);
  126.         }
  127.         return;
  128.     }
  129.  
  130.     if(mark[r][c]==0){
  131.         mark[r][c]=1;
  132.  
  133.         if(c<C-1 && sol[r][c+1]==1){
  134.             matPathR(r,c+1,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
  135.         }
  136.         if(c>=1 && sol[r][c-1]==1 && mark[r][c-1]==0){
  137.             matPathR(r,c-1,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
  138.         }
  139.         if(r>=1 && sol[r-1][c]==1 && mark[r-1][c]==0){
  140.             matPathR(r-1,c,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
  141.         }
  142.         if(r<R-1 && sol[r+1][c]==1){
  143.             matPathR(r+1,c,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
  144.         }
  145.         if(c>=1 && r>=1 && sol[r-1][c-1]==1 && mark[r-1][c-1]==0){
  146.             matPathR(r-1,c-1,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
  147.         }
  148.         if(c<C-1 && r<R-1 && sol[r+1][c+1]==1){
  149.             matPathR(r+1,c+1,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
  150.         }
  151.         if(r<R-1 && c>=1 && sol[r+1][c-1]==1 && mark[r+1][c-1]==0){
  152.             matPathR(r+1,c-1,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
  153.         }
  154.         if(c<C-1 && r>=1 && sol[r-1][c+1]==1 && mark[r-1][c+1]==0){
  155.             matPathR(r-1,c+1,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
  156.         }
  157.         mark[r][c]=0;
  158.     }
  159.     return;
  160. }
  161.  
  162.  
  163. void alfiere(int *r, int *c, int **m, int row, int col){
  164.     int i,j, bSum=0, s;
  165.  
  166.     for(i=0;i<row;i++){
  167.         for(j=0;j<col;j++){
  168.             if(m[i][j]==0){
  169.                 s=sommaDiag(i,j,m,row,col);
  170.                 if(s>bSum){
  171.                     bSum=s;
  172.                     *r=i;*c=j;
  173.                 }
  174.             }
  175.         }
  176.     }
  177.     return;
  178. }
  179.  
  180. int sommaDiag(int r, int c, int** m, int row, int col){
  181.     int s=0, i, j;
  182.  
  183.     for(i=r, j=c;i<row && j<col;i++,j++){
  184.         s=s+m[i][j];
  185.     }
  186.     for(i=r, j=c;i>=0 && j>=0;i--,j--)
  187.         s=s+m[i][j];
  188.     for(i=r,j=c;i>=0 && j<col; j++, i--)
  189.         s=s+m[i][j];
  190.     for(i=r, j=c; j>=0 && i<row; i++, j--)
  191.         s=s+m[i][j];
  192.  
  193.     return s;
  194. }
  195.  
  196.  
  197. int TREEisomorph(struct node *t1, struct node *t2){
  198.     int n=1;
  199.  
  200.     if((t1->l==NULL && t2->l!=NULL) || (t1->l!=NULL && t2->l==NULL))return 0;
  201.  
  202.     if((t1->r==NULL && t2->r!=NULL) || (t1->r!=NULL && t2->r==NULL))return 0;
  203.  
  204.     if(!KEYcmp(t1->k, t2->k))return 0;
  205.  
  206.     if(t1->l!=NULL)
  207.         n&=TREEisomorph(t1->l,t2->l);
  208.     if(t2->r!=NULL)
  209.         n&=TREEisomorph(t1->r,t2->r);
  210.     return n;
  211. }
  212.  
  213. int KEYcmp(char c1, char c2){
  214.     return c1==c2;
  215. }
  216.  
  217. struct node *leggiAlb(char *file){
  218.     FILE *fp;
  219.  
  220.     fp=fopen(file,"r");if(fp==NULL)exit(-1);
  221.     return albreadR(fp);
  222. }
  223.  
  224. struct node *albreadR(FILE *fp){
  225.     int dx, sx;
  226.     char k;
  227.     struct node *h;
  228.  
  229.     if(fscanf(fp,"%c %d %d",&k,&sx,&dx)==EOF)return NULL;
  230.     h=NEW(k);
  231.     if(sx)
  232.         h->l=albreadR(fp);
  233.     if(dx)
  234.         h->r=albreadR(fp);
  235.     return h;
  236. }
  237.  
  238. struct node *NEW(char k){
  239.     struct node *tmp;
  240.     tmp=malloc(sizeof*tmp);
  241.     tmp->k=k;
  242.     tmp->l=NULL;
  243.     tmp->r=NULL;
  244.     return tmp;
  245. };
RAW Paste Data