Labirint
Aşağıdakı labirinti nəzərdən keçirin, bərabərtərəfli üçbucaqlardan ibarətdir:
Hər bir zirvə şəkildə göstərildiyi kimi iki koordinat x və y ilə təsvir olunur. Bəzi kənarlarda ağ və ya qara dairələr var. Labirintdə hərəkəti idarə edən iki əsas qayda var:
Yalnız dairələr olan kənarlardan keçməyə icazə verilir.
Labirintdə hərəkət edərkən ağ və qara dairələri növbələmək məcburidir; yəni, son keçilən dairə qara olduqda yalnız ağ dairəsi olan kənardan keçməyə icazə verilir və əksinə. İlk hərəkət zamanı qara və ya ağ dairəsi olan kənardan keçməyə icazə verilir.
Labirintdə giriş nöqtəsindən çıxış nöqtəsinə qədər ən qısa yolun uzunluğunu tapmaq üçün bir proqram yazın. Yolun uzunluğu keçilən kənarların (və ya dairələrin) sayı kimi müəyyən edilir. Belə bir yolun həmişə mövcud olduğunu qəbul edə bilərsiniz.
Giriş verilənləri
Birinci sətir labirintin eni və hündürlüyü olan iki tam ədəd W və H ehtiva edir (1 ≤ W, H ≤ 500). İkinci sətir dörd tam ədəd: X_1 Y_1 X_2 Y_2 (0 ≤ X_1, X_2 ≤ W; 0 ≤ Y_1, Y_2 ≤ H) ehtiva edir. (X_1, Y_1) labirintin giriş nöqtəsinin koordinatları və (X_2, Y_2) çıxış koordinatlarıdır.
Növbəti 2H+1 sətir kənarların təsvirini təqdim edir: tək sətirlər (3^cü, 5^ci və s.) üfüqi kənarları, cüt sətirlər (4^cü, 6^cı və s.) qeyri-üfüqi kənarları təsvir edir. Hər bir sətir n, w və b simvollarından ibarət bir sətirdir, burada n kənarda dairə olmadığını, w və ya b isə müvafiq olaraq ağ və ya qara dairə olduğunu bildirir. Bu simvollar arasında boşluq yoxdur. Təbii ki, tək sətirlər dəqiq W simvoldan, cüt sətirlər isə dəqiq 2W+1 simvoldan ibarətdir.
Çıxış verilənləri
Proqramınız çıxış faylının birinci (və yeganə) sətrində giriş nöqtəsindən çıxış nöqtəsinə qədər ən qısa yolun uzunluğunu göstərən bir tam ədəd çıxarmalıdır.
Şərh
1: Sadə bir labirint. Mümkün olan ən qısa yollardan biri budur:
(0, 0) → (1, 0) → (0, 1) → (1, 1) → (1, 0) → (2, 0) → (2, 1)
Burada labirintin və ən qısa yolun təsviri:
2: Bu, birinci səhifədəki şəkildə verilmiş labirintin təsviridir. Ən qısa yol budur:
(0, 2) → (1, 2) → (1, 1) → (2, 1) → (2, 0) → (3, 0) → (3, 1) → (3, 2) → (4, 1) → (3, 1) → (3, 0) → (2, 0) →
→ (2, 1) → (1, 1) →(1, 2) → (1, 3) → (2, 3) → (2, 4) → (3, 4) → (3, 3) → (4, 3) → (4, 2) → (5, 2)
(Uzunluq: 22)