CSES - Datatähti 2016 alku - Tontti
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Uolevi haluaa ostaa metsästä tontin, joka on neliön muotoinen ja jossa on tarkalleen xx puuta. Kuinka monta tapaa Uolevilla on tontin valintaan?

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua nn, mm ja xx: metsän korkeus, metsän leveys ja haluttu puiden määrä.

Tämän jälkeen syötteessä on nn riviä, joista jokaisella on mm merkkiä. Nämä rivit kuvaavat metsän. Merkki . tarkoittaa tyhjää kohtaa, ja merkki * tarkoittaa puuta.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: montako tapaa Uolevilla on tontin valintaan?

Esimerkki

Syöte:

4 6 3
..**..
**....
*...*.
..*...

Tuloste:

3

Rajat

Kaikissa osatehtävissä pätee:

  • 0xnm0 \le x \le n \cdot m

Osatehtävä 1 (14 pistettä)

  • 1n,m101 \le n, m \le 10

Osatehtävä 2 (33 pistettä)

  • 1n,m5001 \le n, m \le 500

Osatehtävä 3 (53 pistettä)

  • 1n,m20001 \le n, m \le 2000