[C] Aiuto, non riesco a risolvere questo problema

[Ir0nM4id3n84]

Ciao,
devo fare questo programma per l'università e stò impazzendo, non riesco a trovare una strategia per risolverlo....mi sento scemoooo :cry:

Descrizione
Una matrice di interi di dimensioni m x n rappresenta le quote di un rilievo topografico. In una certa coordinata è presente una sorgente d'acqua. Sapendo che l'acqua può scendere in tutte le direzioni (verticale, orizzontale, diagonale) verso punti con quota minore o uguale, ma ovviamente non può salire, determinare tutte le zone che saranno allagate.
Il vostro programma dovrà:


Input
accettare in input le dimensioni della matrice (due interi, prima il numero di righe, poi il numero di colonne);
accettare in input m x n valori interi che rappresentano le quote (la matrice viene letta per righe).
accettare in input le coordinate della sorgente (due interi, prima la riga, poi la colonna)

Output
produrre in output una matrice con le stesse dimensioni di quella inserita in input, in cui ci sarà un 2 nella posizione in cui si trova la sorgente d'acqua, 1 in tutti i punti raggiunti dall'acqua, e 0 nei restanti
IMPORTANTE

non far produrre al programma altri output oltre a quelli richiesti.
stampare gli elementi della matrice di output con il formato:

%3d


Ecco un esempio di input del programma (i primi due numeri sono le dimensioni della matrice, i successivi 15 gli elementi della matrice e gli ultimi due la posizione della sorgente d'acqua):


5
3
8
1
7
4
6
1
2
9
8
3
7
6
1
9
2
0
2
La matrice che non dovete stampare è la seguente:

8 1 7 4 6
1 2 9 8 3
7 6 1 9 2

Con questi dati di ingresso, l'output prodotto dovrà essere il seguente:


0 1 2 1 0
1 1 0 0 1
0 0 1 0 1

[Blackat]

domanda: che studi fai ?

[repne scasb]

[Ir0nM4id3n84]

Io studio informatica, avevo specificato nel titolo che si trattava di linguaggio C. Sono 2 giorni che mi spremo le meningi a trovare una soluzione ricorsiva ma non ci sono riuscito....cmq grazie dell'aiuto....hai detto che ne hai dati tanti?insengi?

[Blackat]

Versione ricorsiva....


#include <stdio.h>
#define m 5
#define n 3

int mappa[n][m] = { {8,1,7,4,6}, {1,2,9,8,3}, {7,6,1,9,2} };
int acqua[n][m];
int x_sorgente, y_sorgente,i,j;


void segna(int x,int y);
int main() {
x_sorgente = 0;
y_sorgente = 2;
acqua[x_sorgente][y_sorgente]=2;

segna(x_sorgente,y_sorgente);

for ( i = 0; i < n; i++)
{
for ( j = 0; j < m; j++) {
printf("%d ",acqua[i][j]);
}
printf("\n");
}
return 0;
}

void segna(int x,int y) {


if ( x >= 0 && y>=0 && x < n && y < m ) {

if ( acqua[x][y] != 0 ) {

if ( ( x-1 ) >= 0 && ( y -1 ) >= 0 && mappa[x-1][y-1] < mappa[x][y] ) {
acqua[x-1][y-1] = 1;
segna(x-1,y-1);
}

if ( ( x-1 ) >= 0 && mappa[x-1][y] < mappa[x][y] ) {
acqua[x-1][y] = 1;
segna(x-1,y);
}

if ( ( x-1 ) >= 0 && ( y + 1 ) < m && mappa[x-1][y+1] < mappa[x][y] ) {
acqua[x-1][y+1] = 1;
segna(x-1,y+1);
}


if ( ( y-1 ) >= 0 && mappa[x][y-1] < mappa[x][y] ) {
acqua[x][y-1] = 1;
segna(x,y-1);
}

if ( ( y+1 ) < m && mappa[x][y+1] < mappa[x][y] ) {
acqua[x][y+1] = 1;
segna(x,y+1);
}


if ( ( x+1 ) < n && ( y -1 ) >= 0 && mappa[x+1][y-1] < mappa[x][y] ) {
acqua[x+1][y-1] = 1;
segna(x+1,y-1);
}

if ( ( x+1 ) < n && mappa[x+1][y] < mappa[x][y] ) {
acqua[x+1][y] = 1;
segna(x+1,y);
}

if ( ( x+1 ) < n && ( y + 1 ) < m && mappa[x+1][y+1] < mappa[x][y] ) {
acqua[x+1][y+1] = 1;
segna(x+1,y+1);
}


}


}
}


Io sono uno studente universitario in Informatica di Catania.
Posso dire di aver avuto un buon maestro di programmazione.
Poi ho affinato la mia tecnica nel programmare utilizzando
la ricorsione grazie alle lezioni di lambda calcolo. ;-)

:-)

Saluti.


P.S.

Per spiegazioni contattarmi in pvt.

[cionci]

Una soluzione per dimezzare (probabilmente di più) le linee di codice è Farsi un vettore con le possizioni possibili:

int pos[8][2] = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}};

Dopo con un semplice for:

for(i=0; i<8; ++i)
{
if(x-pos[i][0] >= 0 && x-pos[i][0] < m && y-pos[i][1] >= 0 && y-pos[i][1] < n )
if(mappa[x-pos[i][0][y-pos[i][1]] < mappa[x][y])

e così via...in 4 righe i controlli sono fatti ;)

[Blackat]

Effettivamente hai ragione, però non so in che
condizioni il compilatore si comporti.

Immagina che tu hai un vettore di costanti che
devi ogni volta indicizzare. Metti che ci stai t m/s.

Quindi sono mxnxlog(n)xtx8.
Mentre il compilatore, utilizzando la mia versione potrebbe
decidere di trattare, ad esempio un x - 1, come
un ( supponendo che x sia nel registro AX )

DEC AX


che è molto più veloce di accedere alla memoria.

Comunque come leggibilità va di sicuro meglio! ;)

[cionci]

Non ho detto che sia più veloce ;)

[repne scasb]

[Ir0nM4id3n84]

Originariamente inviato da Blackat
Versione ricorsiva....


#include <stdio.h>
#define m 5
#define n 3

int mappa[n][m] = { {8,1,7,4,6}, {1,2,9,8,3}, {7,6,1,9,2} };
int acqua[n][m];
int x_sorgente, y_sorgente,i,j;


void segna(int x,int y);
int main() {
x_sorgente = 0;
y_sorgente = 2;
acqua[x_sorgente][y_sorgente]=2;

segna(x_sorgente,y_sorgente);

for ( i = 0; i < n; i++)
{
for ( j = 0; j < m; j++) {
printf("%d ",acqua[i][j]);
}
printf("\n");
}
return 0;
}

void segna(int x,int y) {


if ( x >= 0 && y>=0 && x < n && y < m ) {

if ( acqua[x][y] != 0 ) {

if ( ( x-1 ) >= 0 && ( y -1 ) >= 0 && mappa[x-1][y-1] < mappa[x][y] ) {
acqua[x-1][y-1] = 1;
segna(x-1,y-1);
}

if ( ( x-1 ) >= 0 && mappa[x-1][y] < mappa[x][y] ) {
acqua[x-1][y] = 1;
segna(x-1,y);
}

if ( ( x-1 ) >= 0 && ( y + 1 ) < m && mappa[x-1][y+1] < mappa[x][y] ) {
acqua[x-1][y+1] = 1;
segna(x-1,y+1);
}


if ( ( y-1 ) >= 0 && mappa[x][y-1] < mappa[x][y] ) {
acqua[x][y-1] = 1;
segna(x,y-1);
}

if ( ( y+1 ) < m && mappa[x][y+1] < mappa[x][y] ) {
acqua[x][y+1] = 1;
segna(x,y+1);
}


if ( ( x+1 ) < n && ( y -1 ) >= 0 && mappa[x+1][y-1] < mappa[x][y] ) {
acqua[x+1][y-1] = 1;
segna(x+1,y-1);
}

if ( ( x+1 ) < n && mappa[x+1][y] < mappa[x][y] ) {
acqua[x+1][y] = 1;
segna(x+1,y);
}

if ( ( x+1 ) < n && ( y + 1 ) < m && mappa[x+1][y+1] < mappa[x][y] ) {
acqua[x+1][y+1] = 1;
segna(x+1,y+1);
}


}


}
}


Io sono uno studente universitario in Informatica di Catania.
Posso dire di aver avuto un buon maestro di programmazione.
Poi ho affinato la mia tecnica nel programmare utilizzando
la ricorsione grazie alle lezioni di lambda calcolo. ;-)

:-)

Saluti.


P.S.

Per spiegazioni contattarmi in pvt.

Il problema è che sio deve allagare anche quando le due quote vicine siano uguali e così il tuo programma non funziona

[cionci]

Se hai capito come funziona il programma ci vuole pochissimo per modificarlo ;)

[Blackat]

Grande Cionci! ;)