Labirint#3014

Labirint

1 saniyə

64 meqabayt

Asan

Aşağıdakı bərabərtərəfli üçbucaqlardan ibarət labirinti nəzərdən keçirin:

Hər bir zirvə şəkildə göstərildiyi kimi iki $x$ və $y$ koordinatı ilə göstərilir. Bəzi kənarlarda ya ağ, ya da qara dairələr var. Labirintdə hərəkəti tənzimləyən iki əsas qayda mövcuddur:

Yalnız üzərində dairə olan kənarlarla hərəkət etmək icazəlidir.
Labirintdə hərəkət edərkən, ağ və qara dairələr arasında növbələmək lazımdır: yəni, yalnız sonuncu keçdiyiniz dairə qara olubsa, ağ dairə olan kənarı, və əksinə, keçmək olar. İlk hərəkətdə isə istər qara, istərsə də ağ dairə olan kənarla başlamağa icazə verilir.

Proqram yazın ki, daxilolma nöqtəsindən çıxışa qədər olan ən qısa yolun uzunluğunu tapsın. Yolun uzunluğu keçilən kənarların (və ya dairələrin) sayına bərabərdir. Qəbul edin ki, belə bir yol həmişə mövcuddur.

Giriş

Birinci sətirdə labirintin eni $W$ və hündürlüyü $H$ olan iki tam ədəd verilir ( $1 \leq W, H \leq 500$ 1 \leq W, H \leq 500). İkinci sətirdə dörd tam ədəd verilir: $X_{1} Y_{1} X_{2} Y_{2}$ X_1\ Y_1\ X_2\ Y_2 ( $0 \leq X_{1}, X_{2} \leq W$ 0 \leq X_1, X_2 \leq W; $0 \leq Y_{1}, Y_{2} \leq H$ 0 \leq Y_1, Y_2 \leq H). $(X_{1}, Y_{1})$ (X_1, Y_1) giriş nöqtəsinin koordinatları, $(X_{2}, Y_{2})$ (X_2, Y_2) isə çıxış nöqtəsinin koordinatlarıdır.

Növbəti $2 H + 1$ 2H+1 sətir kənarları təsvir edir: tək nömrəli sətirlər ( $3$ -cü, $5$ -ci və s.) üfüqi kənarları, cüt nömrəli sətirlər ( $4$ -cü, $6$ -cı və s.) isə qeyri-üfüqi kənarları göstərir. Hər belə sətirdə $n$ , $w$ və $b$ simvollarından istifadə olunur: $n$ – həmin kənarda dairə yoxdur, $w$ və ya $b$ isə müvafiq olaraq həmin kənarda ağ və ya qara dairə olduğunu göstərir. Simvollar arasında boşluq yoxdur. Konkret olaraq, tək nömrəli sətirlərdə dəqiq $W$ simvol olur, cüt nömrəli sətirlərdə isə dəqiq $2 W + 1$ 2W+1 simvol olur.

Çıxış

Çıxışda yeganə ədədi çap edin — başlanğıc nöqtəsindən çıxışa qədər mümkün olan ən qısa yolun uzunluğunu.

Şərh

1: Sadə bir labirint. Mümkün olan ən qısa yollardan biri:

$(0, 0) \to (1, 0) \to (0, 1) \to (1, 1) \to (1, 0) \to (2, 0) \to (2, 1)$ (0, 0) \to (1, 0) \to (0, 1) \to (1, 1) \to (1, 0) \to (2, 0) \to (2, 1)

Aşağıda labirintin və ən qısa yolun təsviri göstərilib:

2: Bu, birinci səhifədəki şəkildə olan labirintdir. Ən qısa yol belədir:

$(0, 2) \to (1, 2) \to (1, 1) \to (2, 1) \to (2, 0) \to (3, 0) \to (3, 1) \to (3, 2) \to (4, 1) \to (3, 1) \to (3, 0) \to (2, 0)$ (0, 2) \to (1, 2) \to (1, 1) \to (2, 1) \to (2, 0) \to (3, 0) \to (3, 1) \to (3, 2) \to (4, 1) \to (3, 1) \to (3, 0) \to (2, 0)

$\to (2, 1) \to (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 4) \to (3, 4) \to (3, 3) \to (4, 3) \to (4, 2) \to (5, 2)$ \to (2, 1) \to (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 4) \to (3, 4) \to (3, 3) \to (4, 3) \to (4, 2) \to (5, 2)

(Uzunluq: $22$ )

Nümunələr

Nümunə 1