Fişka oyunu
Siz yeni bir kompüter oyununun inkişaf etdiricilərindən birisiniz. Oyun W×H ölçülü hüceyrələrdən ibarət düzbucaqlı lövhədə baş verir. Hər bir hüceyrə ya fişka ehtiva edə bilər, ya da etməyə bilər (şəkilə baxın).
Oyunun əsas məqsədlərindən biri, iki fişkanın aşağıdakı şərtlərə uyğun bir yol ilə birləşdirilib-birləşdirilmədiyini yoxlamaqdır:
Yol şaquli və üfüqi düz xətlərin seqmentlərindən ibarət olmalıdır.
Yol digər fişkaları keçməməlidir.
Bu zaman yolun bir hissəsi lövhədən kənarda ola bilər. Məsələn:
Koordinatları (1,3) və (4, 4) olan fişkalar birləşdirilə bilər. Koordinatları (2, 3) və (5, 3) olan fişkalar da birləşdirilə bilər. Lakin koordinatları (2, 3) və (3, 4) olan fişkaları birləşdirmək mümkün deyil – onları birləşdirən istənilən yol digər fişkaları keçir.
Sizdən tələb olunan, verilən şərtlərə uyğun bir yol ilə iki fişkanı birləşdirib-birləşdirə bilməyəcəyinizi yoxlayan bir proqram yazmaqdır və müsbət cavab halında belə bir yolun minimal uzunluğunu müəyyən etməkdir (yolun qıvrımları, başlanğıcı və sonu yalnız hüceyrələrin mərkəzlərində (və ya lövhədən kənarda yerləşən "xəyali hüceyrələrdə") olmalıdır və iki qonşu hüceyrənin mərkəzlərini birləşdirən seqmentin uzunluğu 1 hesab olunur).
Giriş verilənləri
Giriş faylının ilk sətiri iki natural ədəd ehtiva edir: W – lövhənin eni, H – lövhənin hündürlüyü (1 ≤ W, H ≤ 75). Növbəti H sətir lövhənin təsvirini ehtiva edir: hər bir sətir dəqiq W simvoldan ibarətdir: "X" simvolu (böyük ingilis hərfi "X") fişkanı göstərir, "." simvolu boş yeri göstərir. Bütün digər sətirlər sorğuların təsvirini ehtiva edir: hər bir sorğu dörd natural ədəddən ibarətdir, boşluqlarla ayrılmışdır – X_1, Y_1, X_2, Y_2, burada 1 ≤ X_1, X_2_{ }≤ W, 1 ≤ Y_1, Y_2_{ }≤ H. Burada (X_1, Y_1) və (X_2, Y_2) birləşdirilməsi lazım olan fişkaların koordinatlarıdır (sol üst hüceyrənin koordinatları (1,1)-dir). Bu koordinatların üst-üstə düşməyəcəyi təmin edilir (sonuncu sorğu istisna olmaqla; baxın aşağıda). Sonuncu sətir dörd ədəd 0 olan bir sorğu ehtiva edir; bu sorğunu işləmək lazım deyil. Sorğuların sayı 20-dən çox deyil.
Çıxış verilənləri
Hər bir sorğu üçün ayrıca sətirdə bir tam ədəd çıxış etməlisiniz – ən qısa yolun uzunluğu və ya belə bir yol mövcud deyilsə 0.