Masala #0533

Xotira 10 MB Vaqt 500 ms
14

Nokia Racing GaMe #2

Eski Nokia telefonlaridagi Racing o'yini yodingizdami? O'yin shartlari quyidagicha.

  1. O'yin NxN kenglikdagi yo'lakchada bo'lib o'tadi;
  2. O'yinda poyga mashinasi (1, 1) katakchadan yurishni boshlaydi.
  3. Mashina chap, o'ng va pastga harakatlana oladi.
  4. Finish (N, N) katakcha hisoblanadi.

Siz mashina "Finish"ga yetib borishi uchun eng kamida necha marotaba harakatni amalga oshirishi kerak ekanligini topishingiz kerak. 

 


Kiruvchi ma'lumotlar:

Kiruvchi ma'lumotlarning birinchi satrida o'yin o'ynaladigan yo'lakning o'lchami \(N\)\((2\leq N\leq 50)\). Keyingi \(N\) ta satrda \(N\) tadan belgi, bu belgilar ikkita belgini o'z ichiga oladi, * bu yurish mumkun bo'lgan katakcha, # bu esa to'siq mavjud bo'lgan katakchani ifodalaydi.


Chiquvchi ma'lumotlar:

Chiqish faylida o'yinda mashina Finishga yetib borishi uchun minimal harakatni chop eting, agar yetib borishning imkoni bo'lmasa -1 ni chop eting.


Misollar
# input.txt output.txt
1
5
**#**
#****
***#*
*##**
*****
8