Gozdovi

Osnovne informacije

Omejitve
  • Čas: 5 s
  • Spomin: 512 MB
Avtor:
  • Jure Slak
  • UPM 2019

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Kako lepó bi biló
romati vse življenje
skozi zeleni gozd
in se ne ustaviti.
— Srečko Kosovel, Kako lepo

Dobili ste satelitske slike slovenskih gozdov. Slika je karirasta mreža, ki je sestavljena iz kvadratov velikosti 1\text{ km} \times 1 \text{ km}. Za vsak kvadrat (s površino 1 \text{ km}^2) je označeno, katere vrste dreves prevladujejo na njem. Za vsako satelitsko sliko morate povedati, koliko različnih gozdov se nahaja na njej. Gozd je definiran kot največje povezano območje iste prevladujoče vrste dreves. Dva kvadrata dreves sta sosedna, če si delita stranico ali oglišče.

Vhodni podatki

V prvi vrstici sta dani s presledkom ločeni nenegativni celi števili n_1 in m_1. Sledi slika velikosti n_1 \times m_1. Slika je sestavljena iz n_1 vrstic; vsaka vrstica vsebuje m_1 znakov, ki označujejo prevladujoči gozd na pripadajočem kvadratu. Nato sledita s presledkom ločeni nenegativni celi števili n_2 in m_2 ter nova slika velikosti n_2 \times m_2. Vhod se zaključi, ko velja n_i = m_i = 0.

Omejitve vhodnih podatkov

  • 0 \leq n_j, m_j
  • \sum_j\; n_jm_j \leq 250\,000
  • Prevladujoče vrste dreves so označene z velikimi črkami angleške abecede.

Izhodni podatki

Za vsako sliko izpišite po eno vrstico, ki naj vsebuje število gozdov na njej.

Primer

Vhod

4 5
BHHHK
HBHKK
LLLLL
GGLGG
1 3
JJJ
0 0

Izhod

6
1

Komentar

Na prvi sliki proti severozahodu vidimo brezov gozd, ki se prepleta s hrastovim, toda na vzhodu se ta začne prelivati v kostanjev gozd. Južno od tega je pas, primeren za rast lipe, ki se dovolj zajeda v obronke gabra na jugu, da ga je razdelila v dva ločena gozdova. Na sliki tako vidimo 6 gozdov: bukovega, hrastovega, kostanjevega, lipovega in dva gabrova. Na drugi sliki imamo samo jesenov gozd.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task