CSES - Hirviöt
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Olet $n \times n$ ruudukon vasemmassa ylänurkassa ja tavoitteesi on päästä oikeaan alanurkkaan. Saat liikkua ruudukossa oikealle ja alaspäin.

Jokaisessa ruudussa on merkki . (tyhjä) tai * (hirviö). Jos menet ruutuun, jossa on hirviö, joudut tappeluun sen kanssa.

Mikä on pienin määrä hirviöitä reitillä vasemmasta ylänurkasta oikeaan alanurkkaan?

Syöte

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

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

Tuloste

Tulosta yksi kokonaisluku: pienin määrä hirviöitä.

Rajat
  • $1 \le n \le 2500$
Esimerkki

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


Tuloste:
1