[C++] Matrici

[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