Preskoči na glavno vsebino
Učilnica FRI 24/25
  • Domov
  • Več
Zapri
Preklopi iskalni vnos
Slovenščina ‎(sl)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
Trenutno uporabljate gostujoči dostop
Prijavite se
Učilnica FRI 24/25
Domov
Razširi vse Skrči vse
  1. aps1uni
  2. Grafi
  3. Celine

Celine

Zahteve zaključka
Rok za oddajo: nedelja, 12. november 2023, 23.59

Podan je zemljevid v obliki pravokotne mreže višine $H$ in širine $W$. Za vsako polje $Z_{i,j}$ vemo, ali je tam morje ali kopno. Povezane celice kopnega formirajo celine. Dve celici kopnega pripadata isti celini, če med njima obstaja pot po kopnih celicah, kjer imajo zaporedne celice na poti skupno stranico. Napišite program, ki bo izračunal velikosti celin (število pripadajočih celic) na podanem zemljevidu.

Omejitve podatkov:

  • $1 \leq H \cdot W \leq 10^5$

Vhodni in izhodni podatki:

V prvi vrstici se nahajata višina zemljevida $H$ in njegova širina $W$. V $i$-ti izmed sledečih vrstic ustreza $j$-ti znak polju $Z_{i,j}$ na zemljevidu in je enak '.', če je na tem mestu morje, ali '#', če je tam kopno.

Izpišite velikosti celin urejene po velikosti od manjših proti večjim in ločene s presledkom.

Primer vhoda:

6 10
######....
#....#.##.
#.##.#..##
#....#..##
######.#..
..#...#..#

Pravilen izhod:

1 1 1 2 6 19
Trenutno uporabljate gostujoči dostop (Prijavite se)
Pridobi mobilno aplikacijo
Stran poganja Moodle
Obvestilo o avtorskih pravicah