Masala E

Bir sirli qahramon o‘rmon bo‘ylab xavfli hududdan qochmoqda. O‘rmonning ba’zi katakchalarida daraxtlar bor. Qahramonimiz biladiki ba'zi daraxtlar ortida sirli tuzoqlar bor ammo aynan qaysi daraxtlar ortida tuzoq borligini bilmaydi, shu sababli daraxtlardan iloji boricha uzoqroq yurishi kerak. Qahramonning maqsadi o'zining xavfsiz uyi joylashgan katakchaga yetib borish, shu bilan birga daraxtlardan iloji boricha uzoq yo‘l tanlash.

O‘rmonni\(N\times M\) katakchali panjara bilan ifodalash mumkin:

• Bo‘sh katakchalar: .
• Daraxtlar: +
• Qahramonning hozirgi joyi: S
• Uy: U

Qahramon har bir qadamda shimol, janub, sharq yoki g'arbga harakat qilishi mumkin, hatto daraxt ustidan ham o‘tishi mumkin.

Agar qahramon \((R, C)\) katakchada bo‘lsa va daraxt \((A, B)\) katakchada bo‘lsa, ular orasidagi masofa quyidagicha:

 \(|R-A|  + |C-B|\)

Qahramon uchun eng xavfsiz yo'l deganda, yo‘l davomida daraxtlardan eng yaqin masofa maksimal bo‘ladigan yo‘l nazarda tutiladi.

• Birinchi qatorda ikkita butun son \(N, M (1\le N, M \le 500)\) – panjaraning o‘lchamlari kiritiladi.
• Keyingi \(N\) ta qatorda \(M\) tadan belgi: ., +, S, U
• Panjarada aniq bitta S, bitta U va kamida bitta + mavjud

Qahramon eng xavfsiz yo‘ldan foydalansa daraxtlargacha bo'lgan eng qisqa masofani chiqaring.