Masala #0524

Xotira 16 MB Vaqt 1000 ms
14

Nokia Racing GaMe

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

  1. O'yin 2xN kenglikdagi yo'lakchada bo'lib o'tadi.
  2. O'yin boshida poyga mashinasi 1-qatorning bo'sh katakchasidan joy oladi.
  3. 2xN yo'lakning har bir qatorining istalgan joyda albatta bitta to'siq bo'ladi.
  4. Mashina oldingi qatorning istalgan to'siqsiz katakchasiga bitta urinishda yura oladi.

Siz mashina "Finish"ga yetib borishi uchun eng kamida nechta urunish amalga oshirishi kerak ekanligini topishingiz kerak.


Kiruvchi ma'lumotlar:

Birinchi satrda o'yin oynaladigan yo'lakdagi qatorlar soni N. Keyingi N ta satrda esa yo'lakdagi gar bir qatorning holati. Bu yerda '*' mashina yurishi mumkin bo'lgan katak, '#' esa shu qatordagi to'siqni bildiradi. 


Chiquvchi ma'lumotlar:

Minimal urinishlar soni.


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