Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Rakennus II

Rakennus II


View task | Model solution | Statistics


Rakennus II

Time limit:1.00 s
Memory limit:128 MB

Uolevi aikoo rakentaa metsään suorakulmion muotoisen talon. Metsässä voi kuitenkin olla puita, eikä talo saa mennä minkään puun päälle.

Tehtäväsi on laskea jokaiselle mahdolliselle talon koolle $a \times b$, montako mahdollista näin suurta tonttia on olemassa.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluvut $n$ ja $m$, jotka määrittävät metsän koon.

Tämän jälkeen syötteessä on metsän kuvaus. Jokainen ruutu on tyhjä (.) tai puu (*).

Tuloste

Tulosta $n$ riviä, joista kullakin on $m$ lukua: halutut tonttien määrät.

Rajat
Esimerkki

Syöte:
4 7
...*.*.
.*.....
.......
......*


Tuloste:
24 17 13 9 6 3 1
16 9 7 5 3 1 0
9 3 2 1 0 0 0
3 0 0 0 0 0 0


Selitys: Esimerkiksi mahdollisia $2 \times 4$ -kokoisia tontteja on $5$ kpl.