Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Käännökset


Task | Statistics


CSES - KäännöksetCSES - Käännökset

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 * (este). Et voi kulkea ruudun kautta, jos siinä on este.

Mikä on pienin määrä käännöksiä 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ä käännöksiä.

Jos mitään reittiä ei ole olemassa, tulosta luku $-1$.

Rajat
Esimerkki

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


Tuloste:
3