Enunțul problemei tsunami, de clasa a 10-a, dată în 2011 la ONI, se găsește pe .campion, PbInfo și InfoArena.

Rezumat tsunami

Avem un teritoriu reprezentat sub formă de matrice cu m linii și n coloane, fiecare element al acesteia reprezentând cota terenului din pătratul corespunzător. Zonele de apă au cota 0, iar cele de uscat cote mai mari decât 0.

Un tsunami este clasificat după înălțimea valului mareic, pe o scară de la 1 la 10. Trebuie să determinăm numărul de zone de pe hartă ce pot fi afectate de un tsunami de înălțime dată, notată cu h. O zonă teritorială este supusă pericolului dacă are cota strict mai mică decât h, și se află în vecinătatea apei sau a altei zone afectate (două pătrate se învecinează dacă au o latură comună).

Soluție tsunami

Este o problemă destul de simplă ce folosește algoritmul de fill. După ce bordăm matricea cu cote mai mari decât înălțimea maximă a unui tsunami (am ales 20), aplicăm câte un fill pentru fiecare poziție cu valoarea 0 din matrice (nici nu are rost să testăm dacă aceasta se învecinează cu apă).

Eu am implementat un fill recursiv. Ca să nu fac stack overflow, am folosit două variabile globale (pentru linie și coloană) în loc de parametri. Dar problema poate fi rezolvată la fel de bine folosind o coadă.

Sursă C++ tsunami

Dacă ai vreo nedumerire cu privire la problema tsunami, lasă un comentariu și te voi ajuta ?

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!