/***   PERCORSI OTTIMALI IN UNA MATRICE         ***/



/*  

Si suppone di avere una matrice di dimensione  row X col.

Ogni cella della matrice e' identificata dalla coppia (r,c),
con  0<= r < row (riga) e  0<= c < col (colonna).


ESEMPIO
=======

In una matrice 3 X 4 le posizioni delle celle sono:

    -------------------------------------
   | (0,0) |  (0,1)  |  (0,2)  |  (0,3)  |
    -------------------------------------
   | (1,0) |  (1,1)  |  (1,2)  |  (1,3)  |
    -------------------------------------
   | (2,0) |  (2,1)  |  (2,2)  |  (2,3)  |
    -------------------------------------







Ad ogni cella (r,c)  e' associato un VALORE, che e' un numero  intero


Un PERCORSO che parte da (r,c) e' ottenuto attraversando r+1 celle della
matrice in questo modo:

- La prima cella e' (r,c)

- Supponiamo  di essere arrivato alla cella (r',c')
 
   Se r'=0 (la cella e' nella prima riga della matrice) il percorso e' terminato
 
   Altrimenti, la prossima cella del percorso deve essere una delle celle
   (r'-1, c') oppure  (r'-1, c'-1) (se e' nella matrice)  oppure  (r'-1, c'+1) (se e' nella matrice).
     
Il VALORE Val(P) di un percorso  P  e' dato dalla somma dei valori delle celle sul percorso.

Un percorso P  da (r,c) e' OTTIMALE se, per ogni altro percorso P' da (r,c),
Val(P') <= Val(P).


ESEMPI
======

Si supponga di avere una matrice 3 X 4 contenente i valori


         0     1    2   3 
     ----------------------
  0 |  200     2  -20   4
  1 |  -10   -10   70   5        
  2 |    0     1    2   3 

Allora:

Esiste un unico percorso ottimale  dalla cella (2,3)

(2,3) -->  (1,2)  --> (0,3)

di valore 77.


Esiste un unico percorso ottimale  dalla cella (2,2)

(2,2) -->  (1,1)  --> (0,0)

di valore 192

Esistono due percorsi ottimali  dalla cella (2,1)

(2,1) -->  (1,1)  --> (0,0)
(2,1) -->  (1,0)  --> (0,0)

di valore 191

Esistono due percorsi ottimali  dalla cella (2,0)

(2,0) -->  (1,0)  --> (0,0)
(2,0) -->  (1,1)  --> (0,0)

di valore 190


*/




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


#define   WORD 50 // Lunghezza massima del nome di un file



/* Crea una matrice di int di dimensione  row X col inizializzata a 0 
   e restituisce l'indirizzo della nuova matrice 
*/

int **newMatr(int row, int col){
  // ....
}




/*  

matr e' una matrice di int di dimensione row X col.

La matrice matr e' inizializzata leggendo una sequenza di interi
contenuta nel file di nome fName. 

Si assume che fName, se esiste, contiene row X col interi separati da spazi.   */

void readMatr(int **matr, int row, int col, char* fName){
  int r,c;
  FILE *fp;
  /* occorre aprire in lettura il file fName */
  fp = fopen(fName,"r");
  if(fp == NULL){
    printf("%s: file inesistente\n", fName);
  }
  else{// lettura di row X col interi dal file associato a  fp   
    for(r=0; r < row ; r++)
      for(c=0; c < col ; c++)
	fscanf(fp, "%d", &matr[r][c]);
    fclose(fp); // il file associato a fp puo' essere chiuso 
  }
 }


/*  Stampa la matrice matr di interi di dimensione  row X col   */

void printMatr(int **matr, int row, int col){
  int r,c;
   for(r=0; r < row ; r++){
    for(c=0; c < col ; c++)
      printf("%5d", matr[r][c]);
    putchar('\n');
  }
}


/****  SOLUZIONE RICORSIVA  *****/


/*   

La funzione calcola ricorsivamente  il valore del percorso ottimale dalla cella (r,c)
in una matrice row X col.
I valori delle celle sono contenuti nella matrice mVal di dimensione  row X col.
Si assume che (r,c) sia una cella della matrice.

*/

int maxPathRic(int r, int c, int **mVal, int row, int col){
  // COMPLETARE
}

/****  SOLUZIONE CON USO DI TABELLE AUSILIARIE (PROGRAMMAZIONE DINAMICA)  *****/

/* 

Data la matrice di valori  mVal  di dimensione  row X col,
vengono calcolati i valori  della matrice  mPathVal  di dimensione  row  X col 
in modo tale che,  per ogni 0<= c <col e  0<= r < row, vale:

-    mPathVal[r][c] = valore del percorso  ottimale  da (r,c)

*/


void setPathVal(int ** mPathVal, int **mVal, int row, int col){
// COMPLETARE
}




/* 

Data la matrice di valori  mVal  di dimensione  row X col,
vengono calcolati i valori  della matrice  mPathVal  di dimensione  row  X col 
e della matrice  mPathDir di dimensione  row  X col in modo tale che: 

- Per ogni 0<= c <col e  0<= r < row

    mPathVal[r][c] =  valore del percorso  ottimale  da (r,c)


- Per ogni 0<= c <col e  0<= r < row-1:

    mPathVal[r][c] = k con k = -1,0,1   se e solo se 
      
    esiste un percorso ottimale         

    (r,c) -->  (r-1,c+k) --> ...

   in cui la cella (r-1,c+k) e' il successore della cella (r,c)
*/


void setPathVal1(int ** mPathVal, int **mPathDir,  int **mVal, int row, int col){
// COMPLETARE
 }


/*

Stampa il percorso ottimale da (r,c) usando la matrice  delle direzioni  mPathDir di dimensione  row  X col 

*/

void printPath(int r, int c, int **mPathDir,   int row, int col){
// COMPLETARE
}




/***  MAIN ***/

int main(){
  int row, col, r,c;
  char fileName[WORD+1]; // serve per leggere il nome del file 
  int** matrVal = NULL;  // matrice dei valori 
  int** matrPathVal = NULL;   // matrice  valori di percorsi ottimali 
  int** matrPathDir = NULL ;  // matrice direzioni percorsi ottimali 


  while((c=getchar())!= 'f'){
    switch(c){
    case 'c':
      if(matrVal!= NULL){ // libera lo spazio delle matrici 
	free(matrVal);
	//free(matrPathVal);
	//free(matrPathDir);
      }
      // INIZIALIZZA LE MATRICI
      scanf("%d%d%s", &row, &col, fileName);
      matrVal = newMatr(row,col);
      readMatr(matrVal, row,col,fileName);
      break;
    case 'p':
      printf("Matrice valori:\n");
      printMatr(matrVal, row,col);
      // printf("Matrice valori dei percorsi ottimali:\n");
      //printMatr(matrPathVal, row,col); // stampa contenuto della matrice matrPathVal  
      // printf("Matrice direzione  dei percorsi ottimali:\n");
      //printMatr(matrPathDir, row,col);  // stampa contenuto della matrice matrPathDir  
      break;
    case 'v':
      scanf("%d%d", &r,&c);
      if(0<=r && r<row && 0<=c && c<col) 
	printf("Valore percorso ottimale da (%d,%d):  %d\n",r,c, maxPathRic(r,c,matrVal, row,col));
      else
	printf("(%d, %d) non e' nella matrice\n",r,c);
      break;
    case 'V':
      // ...
      break;

    } // end switch 
  }// end while 
  return 0;
}