Qnom qəsrdə
Düzbucaqlı N×M ölçülü matrisdə qədim qalanın planı kodlaşdırılıb. Planın hər bir hüceyrəsi A (0 ≤ A ≤ 31) tam ədədi ilə təsvir olunur və bu ədəd aşağıdakı qaydaya əsasən ədədlərin cəmi ilə formalaşır:
1 – qərbdə divar varsa;
2 – şimalda divar varsa;
4 – şərqdə divar varsa;
8 – cənubda divar varsa;
16 - hüceyrədə qızıl kisəsi varsa.
Daxili divar iki hüceyrəyə aid hesab olunur. Məsələn, (1, 2) hüceyrəsinin cənub divarı həm də (2, 2) hüceyrəsinin şimal divarıdır (şəkilə və giriş faylının nümunəsinə baxın).
Müvafiq xarici divarı olmayan xarici hüceyrə çıxış hüceyrəsi adlanır. Şəkildə belə iki hüceyrə göstərilib: (2, 1) və (1, 5). Belə hüceyrələrin sayı ümumilikdə 10-dan çox deyil.
Məlum koordinatları olan (i, j) hüceyrəsində cırtdan yerləşir. O, qalanın divarları mane olmadıqda, qonşu hüceyrələrə ortaq tərəfdən keçərək hərəkət edə bilər. Cırtdan bir qızıl kisəsini götürərək (daha çoxunu daşıya bilməz) istənilən çıxış hüceyrəsinə minimum neçə addım K ilə çata bilər?
Giriş verilənləri
Birinci sətirdə dörd ədəd: N, M – matrisin ölçüsü (1 ≤ N,M ≤ 50) və i, j – cırtdanın koordinatları (1 ≤ i ≤ N, 1 ≤ j ≤ M). Növbəti N sətirdə hər birində M ədəd olmaqla, yuxarıda göstərilən qaydaya uyğun olaraq qalanın planı təsvir edilir.
Çıxış verilənləri
Bir ədəd – çıxışa qədər minimum addım sayı K və ya cırtdan tapşırığı yerinə yetirə bilmirsə -1.