/*
  Programma che genera una matrice casuale formata da 0 e 1 e verifica se
  esiste un percorso (formato dagli 1) che parte dal lato sinistro e arriva al
  lato deestro
*/

#include <iostream.h>
#include <stdlib.h>
#define MAX 5

int percorso=0,mappa[MAX][MAX];    //percorso viene settato a 1 se è stato trovato il percorso
void controllo(int riga, int col=0);

void main()
{
	int i,j;
	randomize();
	for (i=0;i<MAX;i++){           //inizializzazione della matrice
		for (j=0;j<MAX;j++){
			mappa[i][j]=random(2);
		}
	}

	cout<<"\tPalude generata:\n\n";
	for (i=0;i<MAX;i++)       //stampa matrice
	{
		cout<<"\t";
		for (j=0;j<MAX;j++)
			cout << mappa[i][j] << " ";
		cout << endl;
	}

	for (i=0;i<MAX;i++)
		if (mappa[i][0]==1 && percorso==0)
			controllo(i);

	cout << endl << endl;

	if (percorso)
		cout << "\tPercorso trovato:\n\n";
	else
		cout << "\tPercorso inesistente:\n\n";

	for (i=0;i<MAX;i++)
	{
		cout<<"\t";
		for (j=0;j<MAX;j++)
			cout << mappa[i][j] << " ";
		cout << endl;
	}
}

void controllo(int riga, int col)
{
	int i,j;
	mappa[riga][col]=2;

	if (col==MAX-1)
		percorso=1;

	if (mappa[riga-1][col+1]==1 && riga>0 && (col+1)<MAX && percorso==0)
	{
		controllo(riga-1, col+1);
		if (percorso==0)
			mappa[riga-1][col+1]=1;
	}

	if (mappa[riga+1][col+1]==1 && riga<MAX && (col+1)<MAX && percorso==0)
	{
		controllo(riga+1, col+1);
		if (percorso==0)
			mappa[riga+1][col+1]=1;
	}

	if (mappa[riga][col+1]==1 && (col+1)<MAX && percorso==0)
	{
		controllo(riga, col+1);
		if (percorso==0)
			mappa[riga][col+1]=1;
	}

	if (mappa[riga+1][col]==1 && (riga+1)<MAX && percorso==0)
	{
		controllo(riga+1, col);
		if (percorso==0)
			mappa[riga+1][col]=1;
	}

	if (mappa[riga-1][col]==1 && riga>0 && percorso==0)
	{
		controllo(riga-1, col);
		if (percorso==0)
			mappa[riga-1][col]=1;
	}

	if (percorso==0)
		mappa[riga][col]=1;
}