G. Sirli o‘rmon 2: eng qisqa xavfsiz yo‘l
2000 ball
E masaladagi qahramon yana yo‘lga chiqdi, lekin bu safar o‘rmon boshqacha: daraxtlar shunchalik zich o‘sganki, daraxt turgan katakdan o‘tib bo‘lmaydi.
O‘rmon N × M katakli panjara: . — bo‘sh katak, + — daraxt, S — qahramon, U — uy. Har qadamda qo‘shni (shimol, janub, sharq yoki g‘arb) bo‘sh katakka o‘tish mumkin. (R, C) va (A, B) kataklar orasidagi masofa — |R − A| + |C − B| (daraxtlar bu masofani o‘lchashga xalal bermaydi).
Yo‘lning xavfsizligi — yo‘ldagi (S va U ni ham qo‘shib) kataklardan eng yaqin daraxtgacha masofalarning eng kichigi. Qahramon avvalo xavfsizligi eng katta yo‘lni tanlaydi, bunday yo‘llar bir nechta bo‘lsa — ulardan eng qisqasini (qadamlar soni eng kam).
Eng katta xavfsizlik D va o‘sha yo‘lning qadamlar soni K ni toping. Uyga umuman yetib bo‘lmasa, -1 chiqaring.
Kirish ma’lumotlari
Birinchi qatorda N va M. Keyingi N ta qatorning har birida M ta belgi: ., +, S, U.
Chiqish ma’lumotlari
Ikki son D va K bo‘shliq bilan, yoki -1.
Cheklovlar
- 1 ≤ N, M ≤ 500
- panjarada aynan bitta
S, bittaUva kamida bitta+bor
Misollar
5 7 ....... S..+..U ....... ....... .......
3 12
3 3 S+. ++. ..U
-1
Tushuntirish
1-misol: to‘g‘ri yo‘lni daraxt to‘sib turibdi, yuqori qator esa daraxtga juda yaqin (masofa 1). S va U ning o‘zi daraxtdan 3 uzoqlikda, shuning uchun D ≤ 3. Masofa 3 dan kam bo‘lmagan yo‘l faqat pastki qator orqali o‘tadi: 3 qadam pastga, 6 qadam o‘ngga, 3 qadam yuqoriga — K = 12.
2-misol: S ni daraxtlar o‘rab olgan — uyga yetib bo‘lmaydi.