Masala #0533
Nokia Racing GaMe #2
Eski Nokia telefonlaridagi Racing o'yini yodingizdami? O'yin shartlari quyidagicha.
- O'yin NxN kenglikdagi yo'lakchada bo'lib o'tadi;
- O'yinda poyga mashinasi (1, 1) katakchadan yurishni boshlaydi.
- Mashina chap, o'ng va pastga harakatlana oladi.
- 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'lumotlarning birinchi satrida o'yin o'ynaladigan yo'lakning o'lchami . Keyingi ta satrda 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.
Chiqish faylida o'yinda mashina Finishga yetib borishi uchun minimal harakatni chop eting, agar yetib borishning imkoni bo'lmasa -1 ni chop eting.
# | input.txt | output.txt |
---|---|---|
1 |
5 **#** #**** ***#* *##** ***** |
8 |