tutto esame 12_matrice cammino massimo

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define R 3
#define C 3

struct node{
    struct node *l;
    struct node *r;
    char k;
};

int matPath(int **val, int **sol);
void matSolR(int r, int c, int **sol, int **val, int *bSol);
void matPathR(int r, int c, int path,int count,int **val, int** sol, int *bPath, int *bCount, int** mark);
void alfiere(int *r, int *c, int **m, int row, int col);
int sommaDiag(int r, int c, int** m, int row, int col);
int KEYcmp(char c1, char c2);
struct node *leggiAlb(char *file);
struct node *NEW(char k);
struct node *albreadR(FILE *fp);
char *strdup(const char*);
int TREEisomorph(struct node *t1, struct node *t2);
int main()
{

    int bSol=INT_MIN, **sol, i;
    int **val;
    sol=malloc(R*sizeof(int*));
    val=malloc(R*sizeof(int*));
    for(i=0;i<R;i++){
        sol[i]=malloc(C*sizeof(int));
        val[i]=malloc(C*sizeof(int));
    }
    val[0][0]=1;val[0][1]=2;val[0][2]=-3;
    val[1][0]=9;val[1][1]=-9;val[1][2]=7;
    val[2][0]=0;val[2][1]=1;val[2][2]=4;

    matSolR(0,0,sol,val,&bSol);
    printf("Cammino massimo: %d\n",bSol);

    /*
    int r=0,c=0,**val,i;
    val=malloc(4*sizeof(int*));
    for(i=0;i<4;i++){
        val[i]=malloc(4*sizeof(int));
    }
    val[0][0]=0;val[0][1]=3;val[0][2]=4;val[0][3]=0;
    val[1][0]=1;val[1][1]=0;val[1][2]=6;val[1][3]=6;
    val[2][0]=1;val[2][1]=3;val[2][2]=9;val[2][3]=0;
    val[3][0]=0;val[3][1]=0;val[3][2]=3;val[3][3]=1;
    alfiere(&r,&c,val,4,4);
    printf("pos: r=%d c=%d\n",r+1,c+1);
    */
    /*
    struct node *h1;
    struct node *h2;
    int n;
    h1=leggiAlb("alb.txt");
    h2=leggiAlb("alb2.txt");
    n=TREEisomorph(h1,h2);
    printf("res: %d\n",n);

    */
    return 0;
}

void matSolR(int r, int c, int **sol, int **val, int *bSol){
    int n,i;

    if(c==C){
        c=0;
        r++;
    }

    if(r>=R){/*
        for(i=0;i<R;i++){
            for(j=0;j<C;j++){
                printf("%d ",sol[i][j]);
            }
            printf("\n");
        }
        printf("\n");*/

        n=matPath(val,sol);
        if(n>*bSol)
            *bSol=n;
        return;
    }

    for(i=0;i<2;i++){
        sol[r][c]=i;
        matSolR(r,c+1,sol,val,bSol);
    }
    return;
}

int matPath(int **val, int **sol){
    int bPath=INT_MIN, r=0, c=0, bCount=INT_MAX;
    int **mark, i;
    mark=(int**)malloc(R*sizeof(int*));
    for(i=0;i<R;i++)
        mark[i]=(int*)calloc(C,sizeof(int));

    matPathR(r,c,0,0,val,sol,&bPath,&bCount, mark);
    return bPath;
}

void matPathR(int r, int c, int path,int count,int **val, int** sol, int *bPath, int *bCount, int** mark){

    if(sol[r][c]==0 || r<0 || c<0 || r>=R || c>=C)return;

    if(r==R-1 && c==C-1){
        if(sol[r][c])
            path+=val[r][c];

        if(path>*bPath){
            *bPath=path;
            *bCount=count;
            //printf("Passi: %d\n",count);
        }
        if(path==*bPath && count<*bCount){
            *bCount=count;
            //printf("Passi_m: %d\n",count);
        }
        return;
    }

    if(mark[r][c]==0){
        mark[r][c]=1;

        if(c<C-1 && sol[r][c+1]==1){
            matPathR(r,c+1,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
        }
        if(c>=1 && sol[r][c-1]==1 && mark[r][c-1]==0){
            matPathR(r,c-1,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
        }
        if(r>=1 && sol[r-1][c]==1 && mark[r-1][c]==0){
            matPathR(r-1,c,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
        }
        if(r<R-1 && sol[r+1][c]==1){
            matPathR(r+1,c,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
        }
        if(c>=1 && r>=1 && sol[r-1][c-1]==1 && mark[r-1][c-1]==0){
            matPathR(r-1,c-1,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
        }
        if(c<C-1 && r<R-1 && sol[r+1][c+1]==1){
            matPathR(r+1,c+1,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
        }
        if(r<R-1 && c>=1 && sol[r+1][c-1]==1 && mark[r+1][c-1]==0){
            matPathR(r+1,c-1,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
        }
        if(c<C-1 && r>=1 && sol[r-1][c+1]==1 && mark[r-1][c+1]==0){
            matPathR(r-1,c+1,path+val[r][c],count+1,val,sol,bPath,bCount,mark);
        }
        mark[r][c]=0;
    }
    return;
}


void alfiere(int *r, int *c, int **m, int row, int col){
    int i,j, bSum=0, s;

    for(i=0;i<row;i++){
        for(j=0;j<col;j++){
            if(m[i][j]==0){
                s=sommaDiag(i,j,m,row,col);
                if(s>bSum){
                    bSum=s;
                    *r=i;*c=j;
                }
            }
        }
    }
    return;
}

int sommaDiag(int r, int c, int** m, int row, int col){
    int s=0, i, j;

    for(i=r, j=c;i<row && j<col;i++,j++){
        s=s+m[i][j];
    }
    for(i=r, j=c;i>=0 && j>=0;i--,j--)
        s=s+m[i][j];
    for(i=r,j=c;i>=0 && j<col; j++, i--)
        s=s+m[i][j];
    for(i=r, j=c; j>=0 && i<row; i++, j--)
        s=s+m[i][j];

    return s;
}


int TREEisomorph(struct node *t1, struct node *t2){
    int n=1;

    if((t1->l==NULL && t2->l!=NULL) || (t1->l!=NULL && t2->l==NULL))return 0;

    if((t1->r==NULL && t2->r!=NULL) || (t1->r!=NULL && t2->r==NULL))return 0;

    if(!KEYcmp(t1->k, t2->k))return 0;

    if(t1->l!=NULL)
        n&=TREEisomorph(t1->l,t2->l);
    if(t2->r!=NULL)
        n&=TREEisomorph(t1->r,t2->r);
    return n;
}

int KEYcmp(char c1, char c2){
    return c1==c2;
}

struct node *leggiAlb(char *file){
    FILE *fp;

    fp=fopen(file,"r");if(fp==NULL)exit(-1);
    return albreadR(fp);
}

struct node *albreadR(FILE *fp){
    int dx, sx;
    char k;
    struct node *h;

    if(fscanf(fp,"%c %d %d",&k,&sx,&dx)==EOF)return NULL;
    h=NEW(k);
    if(sx)
        h->l=albreadR(fp);
    if(dx)
        h->r=albreadR(fp);
    return h;
}

struct node *NEW(char k){
    struct node *tmp;
    tmp=malloc(sizeof*tmp);
    tmp->k=k;
    tmp->l=NULL;
    tmp->r=NULL;
    return tmp;
};