İş masası

Əməliyyat sisteminin masaüstündə $N$ qısa yol mövcuddur, onların hər biri tam ədədlərlə verilmiş $x$ və $y$ koordinatlarına, həmçinin ada malikdir. Hər bir qısa yolun adı yalnız kiçik latın hərflərindən ($a$–$z$) ibarətdir. Sizin vəzifəniz, hazırda seçilmiş $S$ qısa yolundan hədəf $F$ qısa yoluna klaviatura vasitəsi ilə ən az sayda düymə basmaqla keçməkdir. Hərəkət hərflərdən ($a$–$z$) və ya ox düymələrindən "$\uparrow$", "$\downarrow$", "$\leftarrow$", "$\to$" istifadə etməklə edilir.

Hərf düymələrindən istifadə edərkən seçim aşağıdakı qaydalara əsasən dəyişir:

1. Əgər seçilmiş qısa yolun adı basılan hərflə başlayır və həmin hərflə başlayan bir neçə qısa yol varsa, seçim bu hərflə başlayanlar üzrə lüğəvi ardıcıllıqla növbəti qısa yola keçir (sonuncudan sonra birinciyə geri qayıdır). Məsələn, əgər $a$, $ab$, $b$ qısa yolları varsa, "a" hərfi ancaq $a$ və $ab$ arasında keçid edəcək.

2. Əgər hazırda seçilmiş qısa yolun adı basılan hərflə başlamırsa, seçim həmin hərflə başlayan ən kiçik (lüğəvi olaraq) ada malik qısa yola keçir.

3. Əgər basılan hərflə başlayan heç bir qısa yol yoxdursa, seçim dəyişmir.

Ox düymələrindən istifadə etdikdə, seçim cari qısa yoldan çıxan müvafiq istiqamətdəki ən yaxın qısa yola keçir (Evklid məsafəsinə görə), sektoru sağ bucaq olan istiqamətdə. Bu bucağın bisektrisi oxun istiqamətinə uyğundur. Əgər bir qısa yol sektorun sərhədindədirsə, o, yuxarı/aşağı sektora aid edilir (sol və ya sağ deyil). Əgər sektorda uyğun qısa yol yoxdursa, seçim dəyişmir. Eyni minimal məsafədə bir neçə qısa yol olduqda, $x$ koordinatı ən kiçik olan (əgər bu da eynidirsə, $y$ koordinatı ən kiçik olan) seçilir.

Məsələn, seçilmiş qısa yol $a$ olarsa (şəklə baxın), aşağıdakı keçidlər mümkündür:

1. Ox "$\leftarrow$": Seçim sektordakı ən yaxın qısa yol olan $b$-yə keçir. Yenidən "$\leftarrow$" basdıqda seçim $c$-yə keçir.

2. Ox "$\uparrow$": Sektorda $d$ və $e$ var. Ən yaxın olan $d$-yə keçir.

3. Ox "$\to$": Sektorda yalnız $g$ var, seçim ona keçir.

4. Ox "$\downarrow$": $f$ və $h$ qısa yolları $a$-ya eyni məsafədədir. $x$ koordinatı daha kiçik olan $h$ seçilir. Yenidən "$\downarrow$" basıldıqda, aşağı sektorda başqa qısa yol olmadığından seçim dəyişmir.

DESKTOP adlı proqram tərtib edin, belə ki, qısa yol adları və koordinatları verildikdə, $S$ qısa yolundan $F$ qısa yoluna keçmək üçün lazım olan minimal düymə basmaq sayını hesabləsin.