Corso di Informatica 1 (IN1 - Fondamenti)

Testi e soluzioni di esercizi

 

Percorso sulla matrice

/*
**  percorso.c
**
**  Leggere in input una matrice rettangolare A (100x10),
**  composta da numeri 0 e 1. Verificare se esiste una sequenza
**  di elementi di valore 1 adiacenti tali che si possa
**  individuare un percorso sulla matrice dalla prima all'ultima
**  riga, spostandosi sempre da un elemento di valore 1 ad un
**  altro adiacente, senza mai tornare su righe gia' percorse
**  in precedenza.
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Settembre 2001
*/

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

#define RIGHE 8
#define COL 5

void leggi_matrice(int mat[RIGHE][COL]) {
  int i, j;

  for (i=0; i<RIGHE; i++)
    for (j=0; j<COL; j++)
      scanf("%d", &mat[i][j]);
  return;
}

int percorso(int mat[RIGHE][COL], int i, int j) {
  int risp;

  if (mat[i][j] == 1) {
    if (i==RIGHE-1) {
      risp = 1;
    } else {
      if ((j>0 && percorso(mat, i+1, j-1)) || percorso(mat, i+1, j) || (j<COL-1 && percorso(mat, i+1, j+1)))
        risp = 1;
      else
        risp = 0;
    }
  } else {
    risp = 0;
  }
  return(risp);
}

int main(void) {
  int M[RIGHE][COL], i;

  leggi_matrice(M);
  i=0;
  while (i<COL && !percorso(M, 0, i))
    i++;
  if (i==COL)
    printf("Il percorso NON esiste.\n");
  else
    printf("Il percorso esiste.\n");
  return(1);
}

Per informazioni e commenti: liverani@mat.uniroma3.it - Torna alla Home page - Ultima modifica: 17 Settembre 2001