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. Grafi
  3. Celine

Celine

Completion requirements
Due: Sunday, 12 November 2023, 11:59 PM

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
You are currently using guest access (Log in)
Get the mobile app
Powered by Moodle
Obvestilo o avtorskih pravicah