Salesman in a grid

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/*
questo va in timeout
6 7
4578 5980 5767 3330 2124 218
939 251 2060 9787 8755 6121
5621 3938 3378 1305 8165 9762
67 2270 1097 4242 4043 5411
5154 4046 5506 4022 2976 1924
7383 4948 6637 74 7955 5548
4993 7425 9177 823 8305 6680 8260
2609 8482 9641 1226 355 6570 5245
9293 1555 8737 5765 8430 6262 2081
3349 7134 4314 5506 6326 9921 8248
1882 44 4541 2454 4372 2493 5490
---------------
175540




6 4
0 2 4
6 1 9
4 4 5
3 4 4
2 2 3
5 9 7
3 1 0 6
7 5 1 0
9 0 7 6
0 9 0 6
0 9 9 5
-----------------
87


*/

char *Path;
int PathIdx;
int **Nodi; //[dim][3]; // Array con i nodi e le coordinate e il nome
int path(int r, int c, int col, int **BM, int dim, int rows, int cols, int numCells, int Sum, int **Nodi, int *MinSum);


void freeMatrix(int **M, int r){
    for(int i=0;i<r;i++){
        free(*(M+i));
    }
    free(M);
}

/*
 * Complete the tspGrid function below.
 */
int tspGrid(int horizontal_rows, int horizontal_columns, int** horizontal, int vertical_rows, int vertical_columns, int** vertical) {
    int dim = horizontal_rows*vertical_columns;
    int **BM; // Tabella quadrata bitmapped con tutti i nodi in x e y e le distanze sulle celle.

    int r,c;

    Path= (char *)malloc(dim*sizeof(char));
    BM  = (int**)malloc(dim*sizeof(int*));
    Nodi= (int**)malloc(dim*sizeof(int*));
    for(int i=0; i < dim; i++){
        *(Nodi+i)   = (int *)malloc(3*sizeof(int));
        *(BM+i)     = (int *)malloc(dim*sizeof(int));
    }


    for(int i=0; i<dim; i++){
        r = i/vertical_columns;
        c = i%vertical_columns;
        Nodi[i][0] = r;
        Nodi[i][1] = c;
        Nodi[i][2] = 'a' + i;
        for(int j=0; j<dim; j++){
            BM[i][j] = -1;
        }
    }

    int Ret=0;
    //printf("r*c %d*%d\n",horizontal_rows, vertical_columns);
    // se il numero di celle è pari allora prosegui pure con la ricerca
    // altrimenti sarà impossibile passare su tutte le celle una sola volta
    if ((dim)%2==0){
        Ret = -1; // inizializzo Ret a -1 (infinito)
        // metto i valori di collegamento nella matrice BM
        for(int i=0; i< horizontal_rows; i++){
            for(int j=0; j< horizontal_columns; j++){
                //printf("da %d,%d a %d,%d = %d in %d,%d\n", i, j, i, j+1, *(*(horizontal+i)+j), i*(horizontal_columns+1)+j, i*(horizontal_columns+1)+(j+1));
                BM[i*(horizontal_columns+1)+j][i*(horizontal_columns+1)+(j+1)] = *(*(horizontal+i)+j);
                BM[i*(horizontal_columns+1)+(j+1)][i*(horizontal_columns+1)+j] = *(*(horizontal+i)+j);
            }
        }

        for(int i=0; i< vertical_rows; i++){
            for(int j=0; j< vertical_columns; j++){
                //printf("da %d,%d a %d,%d = %d in %d,%d\n", i, j, i+1, j, *(*(vertical+i)+j), i*vertical_columns+j, (i+1)*vertical_columns+j);
                BM[i*vertical_columns+j][(i+1)*vertical_columns+j] = *(*(vertical+i)+j);
                BM[(i+1)*vertical_columns+j][i*vertical_columns+j] = *(*(vertical+i)+j);
            }
        }

        /*
            BM è la griglia bitmapped con le distanze tra un nodo e l'altro
            la cella di partenza sarà sempre BM[0][1]
            mentre la cella di arrivo deve essere BM[0][columns]
            il percorso sarà chiuso se avrò effettuato rows*columns passaggi
            alla lunghezza calcolata va aggiunto

        */

        PathIdx = -1;
        path(0, 1, 1, BM, dim, horizontal_rows, vertical_columns, 0, 0, Nodi, &Ret);

    }
    /*
    for(int i=0; i<dim; i++){
        printf("%d %d %c\n", Nodi[i][0], Nodi[i][1], Nodi[i][2]);
    }

    for(int i=0; i<dim; i++){
        for(int j=0; j<dim; j++){
            printf("%d ", BM[i][j]);
        }
        printf("\n");
    }
    */
    freeMatrix(BM, dim);
    freeMatrix(Nodi, dim);

    return Ret;
}

int Passato(char c){
    int Found = 0;
    for (int i=0; i<=PathIdx && Found == 0; i++){
        Found = (Path[i]==c?1:0);
    }
    return Found;
}

void StampaPath(){
    for (int i=0; i<=PathIdx; i++){
        printf("%c ", Path[i]);
    }
    printf("\n");
}

int Escludi(int col, int rr, int cc, int rows, int cols){
    int Ret = 0;
    int indexFrom, indexTo;
    if(col==1){
        indexFrom   = cc;
        indexTo     = rr;
    } else {
        indexFrom   = rr;
        indexTo     = cc;
    }
    /*
    printf("%c %c\n", Nodi[cols-2][2], Nodi[cols-1][2]);
    printf("%c %c\n", Nodi[cols-1][2], Nodi[2*cols-1][2]);
    printf("%c %c\n", Nodi[(rows-1)*cols-1][2], Nodi[rows*cols-1][2]);
    printf("%c %c\n", Nodi[rows*cols-1][2], Nodi[rows*cols-2][2]);
    printf("%c %c\n", Nodi[(rows-1)*cols+1][2], Nodi[(rows-1)*cols][2]);
    printf("%c %c\n", Nodi[(rows-1)*cols][2], Nodi[(rows-2)*cols][2]);
    printf("\n");
    */

    if (indexFrom==indexTo)
        return 1;
    else if (indexFrom== 1 && indexTo==0)
        return 1;
    else if (indexFrom== 0 && indexTo!=1)
        return 1;
    else if (indexFrom==cols && indexTo!=0)
        return 1;
    else if (indexFrom==cols-2 && indexTo!=cols-1)
        return 1;
    else if (indexFrom==cols-1 && indexTo!=2*cols-1)
        return 1;
    else if (indexFrom==(rows-1)*cols-1 && indexTo!=rows*cols-1)
        return 1;
    else if (indexFrom==rows*cols-1 && indexTo!=rows*cols-2)
        return 1;
    else if (indexFrom==(rows-1)*cols+1 && indexTo!=(rows-1)*cols)
        return 1;
    else if (indexFrom==(rows-1)*cols && indexTo!=(rows-2)*cols)
        return 1;

    //if (Ret == 0)
        //printf("non bloccato! %c %c\n", Nodi[indexFrom][2], Nodi[indexTo][2]);
     return Ret;
}

int path(int r, int c, int col, int **BM, int dim, int rows, int cols, int numCells, int Sum, int **Nodi, int *MinSum){
    // r,c indica quale cella di BM sto analizzando
    // col indica se devo lavorare per colonna o riga
    int i, j,idx, rr,cc;

    // 1) memorizza in un array tutte le
    int *ch; // scelte possibili max 4
    ch = (int*)malloc(4*sizeof(int));
    memset(ch, 0, 4);

    idx = (col==1?c:r);
    if (Passato(Nodi[idx][2])==0){
        Path[++PathIdx]=Nodi[idx][2];
        //printf("%d %d %c\n", r, c, Nodi[idx][2]);
        for(i=0;i < dim; i++){
            rr  = (col==1?i:r);
            cc  = (col==1?c:i);
            if(BM[rr][cc]!=-1 && Escludi(col, rr, cc, rows, cols)==0){
                Sum += BM[rr][cc];
                numCells++;
                if(rr==0 && cc==1){ // se non sono tornato all'inizio allora continua la ricerca
                    // controlla se ho passato tutte le caselle
                    if (numCells == rows*cols){
                        //printf("percorso OK %d\n", Sum);
                        //StampaPath();
                        // controlla se la somma è inferiore alla somma accumulata
                        if (*(MinSum) == -1 || *(MinSum) > Sum){
                            *(MinSum) = Sum;
                            //printf("percorso chiuso celle %d somma %d\n", numCells, Sum);
                            //StampaPath();

                        }
                    }
                } else {
                    path(rr, cc, (col==1?0:1), BM, dim, rows, cols, numCells, Sum, Nodi, MinSum);
                }
                numCells--;
                Sum -= BM[rr][cc];
            }
        }
        PathIdx--;
    } else {
        //printf("Percorso non valido %c Pathidx %d--------------\n", Nodi[idx][2], PathIdx+1);
        //if (PathIdx > 22)
            //StampaPath();
    }
    free(ch);


    return 0;
}


int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
    int rows, columns;
    int **or, **vr;


    scanf("%d %d", &rows, &columns);
    //printf("%d %d\n", rows, columns);
    or=(int **)malloc(rows*sizeof(int *));
    vr=(int **)malloc(columns*sizeof(int *));

    for(int i=0; i< rows; i++){
        *(or+i) = (int *)malloc((columns-1)*sizeof(int));
        for(int j=0; j< columns-1; j++){
            //scanf("%d", (*(or+i)+j));
            scanf("%d", &or[i][j]);
        }
    }
    for(int i=0; i< rows-1; i++){
        *(vr+i) = (int *)malloc(columns*sizeof(int));
        for(int j=0; j< columns; j++){
            scanf("%d", &vr[i][j]);
        }
    }

    int result = tspGrid(rows, columns-1, or, rows-1, columns, vr);

    fprintf(fptr, "%d\n", result);

    fclose(fptr);
    freeMatrix(or, rows);
    freeMatrix(vr, columns);
    return 0;
}