Skip to main content
Učilnica FRI 24/25
  • Home
  • More
Close
Toggle search input
English ‎(en)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
You are currently using guest access
Log in
Učilnica FRI 24/25
Home
Expand all Collapse all
  1. aps1uni
  2. Vpeta drevesa
  3. Otoki

Otoki

Completion requirements
Due: Sunday, 5 January 2025, 11:59 PM

Podan je zemljevid, na katerem je pokrajina razdeljena na mrežo višine $V$ in širine $S$. Za vsako celico zemljevida je podana njena izmerjena nadmorska višina $H_{i,j} \geq 0$. Hidrologe zanima, kaj se bo zgodilo s pokrajino, če pride do poplav in se gladina vode dvigne do nadmorske višine $P$. Vse celice, ki so višje od gladine vode ($H_{i,j} > P$), so nepoplavljene (višina $H_{i,j}=0$ pomeni, da je celica vedno pod vodo). Nepoplavljene celice pa formirajo otoke. Otoki so množice nepoplavljenih celic, ki so med seboj (posredno) povezane preko skupnih stranic. Napiši program, ki bo za vse možne višine vode izračunal število otokov.

Omejitve podatkov

  • $1 \leq V, S$
  • $V \cdot S \leq 10^5$
  • $0 \leq H_{i,j} \leq 10^5$

Vhodni in izhodni podatki

V prvi vrstici sta podani višina $V$ in širina $S$ zemljevida. Sledečih $V$ vrstic vsebuje $S$ s presledkom ločenih celih števil, ki predstavljajo izmerjene nadmorske višine. V $i$-ti vrstici je $j$-to število izmerjena višina $H_{i,j}$.

Naj bo $P = \max H_{i,j}$ največja podana nadmorska višina. Izpišite $P+1$ vrstic, ki naj po vrsti vsebujejo število otokov pri višini vode $0, 1, ..., P$.

Primer

Vhod:

4 5
7 2 1 0 7
5 8 4 0 2
0 3 1 1 6
2 6 5 0 5

Izhod:

1
2
3
4
4
5
3
1
0
You are currently using guest access (Log in)
Get the mobile app
Powered by Moodle
Obvestilo o avtorskih pravicah