Masala #0487

Xotira 32 MB Vaqt 1000 ms
14

Fors Shaxzodasi Labirintda

Fors shaxzodasi Jafarning labirintiga tushib qoldi. Labirintning eng pastki darajasida malika yashirilgan, shaxzoda malikani qutqarishi uchun K ta darajali labirintni bosib o’tishi zarur bo’ladi. Labirintlar ustma ust joylashgan bo’lib dastlab shaxzoda eng yuqorisida malika esa eng quyi labirintda joylashgan. Barcha labirintlar NxM o’lchamli bo’lib labirintda yo’llar va to’siqlar mavjud. Shaxzoda to’rt tomonga chap\({(L_{z,x,y-1})}\), o’ng\({(L_{z,x,y+1})}\), oldinga\({(L_{z,x+1,y})}\) va orqaga\({(L_{z,x-1,y})}\) harakatlana oladi va o’zi turgan labirintdan pastdagi labirintga sakrashi mumkun agar u turgan koordinata \({(L_{z,x,y})}\) bo’lsa, \({(L_{z+1,x,y})}\)- chi koordinatada to’siq mavjud bo’lmasa. Fors shaxzodasi har bir harakat uchun aynan W-sekun vaqt sarflaydi. Sizning vazifangiz shaxzoda malikani yoniga yetib borishi uchun minimal qancha vaqt sarflashini aniqlash.


Kiruvchi ma'lumotlar:

Kirish fayilining dastlabki satirida to’rtta natural son \(K,N,M,W{(2 \leq K,N,M,W \leq 50)}\) mos ravishda labirintlar soni, labirintni o’lchami va har bir harakat uchun sarflanadigan vaqt.

Kiyin K ta NxM o’lchamli labirintlar kiritiladi har bir labirintdan so’ng bo’sh satir bilan ajratilgan, labirint 4 ta belgidan tashkil topgan bo’lib “o” to’siqni, “.” bu yurish mumkun bo’lgan yo’lni, “1” shaxzodani va “2” esa malikani ifodalaydi.


Chiquvchi ma'lumotlar:

Chiqish fayilida yagona natural son fors shaxzodasi malikani yoniga yetib borishi uchun ketadigan minimal vaqt. Malikani yoniga olib boradigan yo’l mavjud bo’lmasa -1 ni chop eting.


Misollar
# input.txt output.txt
1
3 3 7 5
1...o.o
ooo.ooo
.oooo..

oooo.o.
.o..ooo
...oooo

oooooo.
.2oo..o
oo.o.oo
60