[C++] Matrici

[Ki11aTom]

Salve sto facendo un esercizio di programmazione che riguarda le matrici. Il testo è il seguente:

"La mappa di un territorio viene schematizzata tramite una matrice di dimensioni M per N, all'interno della quale ogni elemento contiene un numero intero che rappresenta in metri l'altezza del terreno in quella zona. In un elemento di cui sono note le coordinate di riga e di colonna, è 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 che non può risalire verso punti di quota superiore, fornire la mappa delle zone che verranno allagate(con un *) e non allagate(con un .) "

Ho pensato di gestire 2 matrici una con le altezze del terreno ed una con i caratteri ("*" e ".")
Inizializzazione tutto OK! la matrice di altezze è acquisita in maniera casuale con numeri da 0 a 9, e la matrice di caratteri la inizializzo con i punti('.')

il mio problema si presenta quando devo scorrere la matrice a partire dalla sorgente. Il primo "ciclo di allagamento" mi torna ma non so poi come aggiornare la sorgente. Come faccio a scorrere una matrice in maniera concentrica a partire dall'elemento centrale?

io ho pensato di fare una cosa del genere ma ovviamente dovrei ripeterlo per ogni elemento della matrice:

matallaga[rs][cs]='*'; // matrice di caratteri da allagare,  allago sorgente
    int i=0,k=0;
    int j=0,z=0;
    
//"matrice" rappresenta la matrice di altezze
// rs rappresenta la riga della sorgente
// cs rappresenta la colonna della sorgente
//vals rappresenta il valore della sorgente


    for(int x=0; x<N*M; x++) { // questo for è sbagliato
        
            i=rs-1;
            j=cs-1;
            for(k=i; k<=rs+1; k++) {
                for(z=j; z<=cs+1; z++) {
                    if(matrice[k][z]<=vals)
                        matallaga[k][z]='*'; // allaga elemento 
                     if(k==rs-1 && z==cs-1) { 
                      // nuova sorgente: riga, colonna e valore
                        nrs=k; 
                        ncs=z;
                        nvals=matrice[k][z];
                    }
                }
            }
            rs=nrs; // aggiorno la sorgente
            cs=ncs;
            vals=nvals;
        
    }

praticamente ogni elemento che si trova intorno alla sorgente diventa la sorgente stessa e così via fino a quando tutti gli elementi della matrice non sono stati confrontati con tutti quelli intorno.

ci sto diventando scemo avrei bisogno di un aiuto

[andrea.xxx]

il mio problema si presenta quando devo scorrere la matrice a partire dalla sorgente. Il primo "ciclo di allagamento" mi torna ma non so poi come aggiornare la sorgente. Come faccio a scorrere una matrice in maniera concentrica a partire dall'elemento centrale?

Secondo me il problema è che ti sei posto il problema sbagliato.
A mio avviso non è necessario partire da un elemento centrale nè muoversi in modo concentrico.
Quello che devi fare è semplicemente allagare tutte le celle adiacenti una cella allagata e aventi altezza inferiore o uguale rispetto a quest'ultima.

Posto un codice di esempio scritto al volo che, anche se compila, non ho testato:

/*
   heights: mappa altezze
   water: zona allagata (true = allagata, false = non allagata)
   width: larghezza (numero colonne)
   height: altezza  (numero righe)
   convenzione: data la cella (i, j) l'altezza è presa da heights[ i + j * width ]
*/
void compute( int const * heights, bool* water, int width, int height )
{
    for( bool new_source = true; new_source;  ) {
        new_source = false;
        for( int x = 0; x < width; ++x ) {
            for( int y = 0; y < height; ++y ) {
                if( ! water[ x + y * width ] ) {
                    continue;
                }
                int h = heights[ x + y * width ];
                for( int i = -1; i < 2; ++i ) {
                    for( int j = -1; j < 2; ++j ) {
                        int x1 = x + i;
                        int y1 = y + j;
                        if( 0 == i && 0 == j ) {
                            continue;
                        }
                        if( x1 < 0 || x1 >= width || y1 < 0 || y1 >= height ) {
                            continue;
                        }
                        int h1 = heights[ x1 + y1 * width ];
                        if( h1 <= h && ! water[ x1 + y1 * width ] ) {
                            new_source = true;
                            water[ x1 + y1 * width ] = true;
                        }
                    }
                }
            }
        }
    }
}

Alcuni commenti sul codice:

Il primo ciclo è eseguito almeno una volta poi richiede che venga trovata almeno una nuova sorgente d'acqua.

I due cicli nidificati su x e y ciclano sull'intera matrice.

Se non c'è sorgente in x,y si passa ad una nuova cella.

Su h salviamo l'altezza della cella corrente quindi testiamo tutte le 8 celle adiacenti attraverso i due cicli su i e j. Chiaramente ignoriamo il caso in cui i ed j sono uguali a zero perchè è la cella attuale!
Saltiamo anche il caso in cui siamo fuori margini della matrice.

La parte importante dell'algoritmo è questa:

int h1 = heights[ x1 + y1 * width ];
if( h1 <= h && ! water[ x1 + y1 * width ] ) {
    new_source = true;
    water[ x1 + y1 * width ] = true;
}

h1 è l'altezza della cella da testare. Per creare una nuova sorgente d'acqua occorre che questa abbia un'altezza minore o uguale alla cella considerata (x, y) e non sia già una sorgente.

Spero ti sia stato di aiuto!

Andrea

[Ki11aTom]

Grazie mille ho capito dove sbagliavo, come sempre cerco di complicarmi la vita inutilmente !!

Grazie ancora !! Ciaoo