Problema Tsunami – ONI 2011, Clasa a 10-a

Problema Tsunami – ONI 2011, Clasa a 10-a

Rezumat

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

Un tsunami este clasificat după înălțimea valului mareic, pe o scară de la 11 la 1010 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 hh O zonă teritorială este supusă pericolului dacă are cota strict mai mică decât hh și se află în vecinătatea apei sau a altei zone afectate (două pătrate se învecinează dacă au o latură comună).

Soluție

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 2020 aplicăm câte un fill pentru fiecare poziție cu valoarea 00 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++

Problema Tsunami
#include <fstream>
#define MAX 20
#define DMAX 1010
std::ifstream fin("tsunami.in");
std::ofstream fout("tsunami.out");
int sol;
int m, n, h;
bool aux[DMAX][DMAX];
short int a[DMAX][DMAX];
// Variabilele folosite de funcția fill:
int I, J;
/// Funcția recursivă de fill
void fill() {
if (a[I][J] < h && !aux[I][J]) {
aux[I][J] = true; // Marcăm poziția în matricea auxiliară.
if (a[I][J]) // Testăm dacă este o zonă uscată.
sol++;
// Aplicăm fill pentru vecini:
I--; fill(); I++;
I++; fill(); I--;
J--; fill(); J++;
J++; fill(); J--;
}
}
/// Funcția de rezolvare
void solve() {
int i, j;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
if (!a[i][j]) {
I = i;
J = j;
fill();
}
}
/// Funcția de citire
void scan() {
int i, j;
fin >> m >> n >> h;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
fin >> a[i][j];
// Bordăm matricea cu MAX:
for (i = 0; i <= m + 1; i++)
a[i][0] = a[i][n + 1] = MAX;
for (j = 0; j <= n + 1; j++)
a[0][j] = a[m + 1][j] = MAX;
}
int main() {
scan();
solve();
fout << sol << '\n';
return 0;
}

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

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii