- 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