/* File: palude.c */
/* Time-stamp: "2002-05-06 00:14:38 calvanes" */
/* Scopo: esercizio significativo sulla ricorsione */

/*
  Data una matrice di 0 e 1 che rappresenta una palude,
  cerca un attraversamento e lo stampa se esiste.

  Variante in cui sono possibili movimenti solo in avanti, cioe`
  da <riga,colonna> a
   - <riga-1, colonna+1>  (solo se la riga non e` la prima)
   - <riga,   colonna+1>
   - <riga+1, colonna+1>  (solo se la riga non e` l'ultima)
*/


#include <stdio.h>

#define R 5  /* numero di righe, cioe` larghezza della palude */
#define C 6  /* numero di colonne, cioe` lunghezza della palude,
                coincide con la lunghezza di un cammino attraverso la palude */


/* Cerca un attraversamento a partire dalla posizione <i,j> della palude.
   Restituisce vero  (1) se l'attraversamento e` stato trovato,
               falso (0) altrimenti.
*/
int cercaCammino (int palude[R][C],      /* la palude */
                  int i, int j,          /* posizione corrente */
                  int cammino[C]);       /* vettore dove mem. cammino tovato */


/* Cerca un attraversamento che porti dalla prima fino all'ultima colonna della
   palude.  Restituisce vero  (1) se l'attraversamento e` stato trovato,
                        falso (0) altrimenti.
 */
int esploraPalude (int palude [R][C],    /* la palude */
                   int cammino[C]);      /* vettore dove mem. cammino tovato */


/* Stampa su video una palude evidenziando un cammino attraverso asterischi.*/
void stampaCammino (int palude [R][C], int cammino[C]);


int main(void)
{
  /* una palude senza cammini */

  int palude[R][C] = {{1,0,0,1,0,0},
                      {0,1,0,0,0,0},
                      {0,0,1,1,0,0},
                      {1,1,0,0,0,0},
                      {1,1,1,0,1,1}};


  /* una palude con un cammino */
  /*
  int palude[R][C] = {{1,0,0,1,0,0},
                      {1,0,0,0,0,0},
                      {0,1,0,0,0,1},
                      {0,0,1,1,1,0},
                      {0,1,0,0,0,0}};
  */

  int cammino[C];            /* vettore dove memorizzare il cammino trovato  */

                                                      /* ricerca del cammino */
  if (esploraPalude(palude, cammino))
    stampaCammino(palude, cammino);
  else
    printf("Non ci sono cammini che attraversano la palude\n");

  return 0;
}


int cercaCammino (int palude[R][C],  /* la palude */
                  int i, int j,      /* posizione corrente */
                  int cammino[C])    /* vettore dove mem. cammino tovato */
  /* Cerca un attraversamento a partire dalla posizione <i,j> della palude.
     Restituisce vero  (1) se l'attraversamento e` stato trovato,
                 falso (0) altrimenti.
  */
{
  int trovato = 0;   /* variabile booleana che memorizza se l'attraversamento
                        e` stato trovato */

  if (palude[i][j] == 1) {                          /* sono sulla terraferma */
    cammino[j] = i;   /* aggiorno la pos. corrente nel cammino da restituire */
    if (j == C-1)     /* sono arrivato dall'altra parte della palude */
      trovato = 1;
    else {                           /* cerco un passaggio nella colonna j+1 */

      if (i > 0)                             /* non sono sulla prima riga;
                                                provo la posizione <i-1,j+1> */
        trovato = cercaCammino(palude, i-1, j+1, cammino);

      if (!trovato)                          /* provo la posizione <i,j+1> */
        trovato = cercaCammino(palude, i, j+1, cammino);

      if (!trovato && i < R-1)               /* non sono sull'ultima riga;
                                                provo la posizione <i+1,j+1> */
        trovato = cercaCammino(palude, i+1, j+1, cammino);
    }
  }

  return trovato;
}


int esploraPalude (int palude [R][C],    /* la palude */
                   int cammino[C])       /* vettore dove mem. cammino tovato */
  /* Cerca un attraversamento che porti dalla prima fino all'ultima colonna
     della palude.
     Restituisce vero  (1) se l'attraversamento e` stato trovato,
                 falso (0) altrimenti.
  */
{
  int i;
  int trovato = 0;  /* variabile booleana che memorizza se l'attraversamento
                       e` stato trovato */

  /* prova a passare per gli elementi della prima colonna, fino a quando non e`
     stato trovato un attraversamento */
  for (i = 0; i < R && !trovato; i++)
    trovato = cercaCammino(palude, i, 0, cammino);

  return trovato;
}


void stampaCammino (int palude [R][C], int cammino[C])
  /* Stampa su video una palude evidenziando un cammino attraverso asterischi.
   */
{
  int i, j;

  for (i=0; i < C; i++)
    printf("%d ", cammino[i]);
  printf("\n\n");

  printf("Cammino che attraversa la palude:\n");
  for (i = 0; i < R; i++) {
    for (j = 0; j < C; j++) {
      printf("%d", palude[i][j]);        /* stampa l'elemento della matrice  */
      if (i == cammino[j])               /* se il punto fa parte del cammino */
        printf("*");                     /*   stampa '*'                     */
      else                               /* altrimenti                       */
        printf(" ");                     /*   stampa uno spazio              */
    }
    printf("\n");
  }
}