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 x puuta. Kuinka monta tapaa Uolevilla on tontin valintaan?

Syöte

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

Tämän jälkeen syötteessä on n riviä, joista jokaisella on m 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:

  • 0 \le x \le n \cdot m

Osatehtävä 1 (14 pistettä)

  • 1 \le n, m \le 10

Osatehtävä 2 (33 pistettä)

  • 1 \le n, m \le 500

Osatehtävä 3 (53 pistettä)

  • 1 \le n, m \le 2000