Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Metsä


Task | Statistics


CSES - MetsäCSES - Metsä

Time limit:1.00 s Memory limit:512 MB

Sinulle on annettu $n \times n$ -ruudukko, joka kuvaa metsän. Jokaisessa ruudussa on merkki . (tyhjä) tai * (puu).

Haluat rakentaa metsään neliön muotoisen rakennuksen, mutta et halua kaataa mitään puuta rakennuksen takia.

Tehtäväsi on laskea jokaiselle rakennuksen koolle $1 \times 1, 2 \times 2, \dots, n \times n$, montako mahdollista paikkaa niin suurelle rakennukselle on metsässä.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: ruudukon koko.

Sitten syötteessä on $n$ riviä, joista jokaisella on $n$ merkkiä: metsän kuvaus.

Tuloste

Tulosta $n$ kokonaislukua: rakennusten paikkojen määrät.

Rajat
Esimerkki

Syöte:
3
..*
...
..*


Tuloste:
7 2 0