Səyahət edən Kub#5791
Kiçik Bandai adlı planetdə, Tadamigawa ulduz gəmisinin eniş qrupu planetin səthində düz sahələrdə hərəkət edən rəngli kublar kəşf etdi və bu sahələri yataq adlandırdılar. Kub müəyyən bir mövqedə yataqda görünür, bir müddət hərəkət edir və sonra yox olur. Uzun müşahidələrdən sonra, Tadamigawa-nın elmi zabiti leytenant Alyssa Ogawa kubun yataqda necə hərəkət etdiyini müəyyən etdi.
Yataq eyni ölçülü kvadratlarla örtülmüş düzbucaqlı bir sahədir.
Kvadratlardan biri qırmızı rəngdədir,
biri yaşıl rəngdədir,
biri mavi rəngdədir,
biri sian rəngdədir,
biri magenta rəngdədir,
biri sarı rəngdədir,
biri və ya bir neçəsi ağ rəngdədir və
qalanları, varsa, qara rəngdədir.
Əvvəlcə kub ağ kvadratlardan birində görünür. Kubun üzləri aşağıdakı kimi rənglənmişdir.
Kub cari kvadratın bir tərəfi ətrafında yuvarlana bilər və beləliklə bitişik kvadrata yuvarlanır. Kub xromatik rəngli (qırmızı, yaşıl, mavi, sian, magenta və ya sarı) kvadrata yuvarlandıqda, yuvarlandıqdan sonra kubun üst üzü eyni rəngdə olmalıdır. Kub ağ kvadrata yuvarlandıqda, belə bir məhdudiyyət yoxdur. Kub heç vaxt qara kvadrata yuvarlanmamalıdır.
Səyahət boyunca, kub hər xromatik rəngli kvadratı yalnız bir dəfə ziyarət edə bilər və ağ kvadratları istənilən sayda ziyarət edə bilər. Artıq qeyd edildiyi kimi, kub heç vaxt qara kvadratları ziyarət edə bilməz. Son xromatik rəngli kvadrata ziyarət zamanı kub yox olur. Necəsə, xromatik rəngli kvadratlara ziyarətlərin sırası səyahət başlamazdan əvvəl bizə məlumdur.
Sizin vəzifəniz kubun verilmiş sırayla bütün xromatik rəngli kvadratları ziyarət etməsi üçün ən az addım sayını tapmaqdır.
Giriş məlumat dəstlərinin ardıcıllığıdır. Məlumat dəsti aşağıdakı kimi formatlanır:
w d
c_11...c_w1
...
c_1d...c_wd
v_1v_2v_3v_4v_5v_6
Birinci sətir boşluqla ayrılmış müsbət tam ədədlər cütü w və d-dir. Növbəti d sətir boşluqsuz w simvoldan ibarət c_11...c_w1, ..., c_1d...c_wd simvollarıdır. Hər bir simvol c_ij r, g, b, c, m, y, w və k hərflərindən biri ola bilər ki, bunlar müvafiq olaraq qırmızı, yaşıl, mavi, sian, magenta, sarı, ağ və qara rəngləri ifadə edir, və ya # işarəsi ola bilər. Hər bir r, g, b, c, m, y və # hər bir məlumat dəstində bir dəfə və yalnız bir dəfə olur. Son sətir "rgbcmy"-nin bir permutasiyası olan altı simvoldan ibarət v_1v_2v_3v_4v_5v_6 simvoludur.
Tam ədədlər w və d yatağın eni (şərq ucundan qərb ucuna qədər olan uzunluq) və dərinliyini (şimal ucundan cənub ucuna qədər olan uzunluq) göstərir. Vahid kvadratın tərəfinin uzunluğudur. Nə w, nə də d 30-dan böyük deyil.
Hər bir simvol c_ij yataqdakı kvadratın rəngini göstərir. Simvollar c_11, c_w1, c_1d və c_wd müvafiq olaraq yatağın şimal-qərb küncünə, şimal-şərq küncünə, cənub-qərb küncünə və cənub-şərq küncünə uyğundur. Əgər c_ij hərfdirsə, bu, müvafiq kvadratın rəngini göstərir. Əgər c_ij # işarəsidirsə, müvafiq kvadrat ağ rəngdədir və kubun ilkin mövqeyidir.
v_1v_2v_3v_4v_5v_6 simvolu ziyarət ediləcək kvadratların rənglərinin sırasını göstərir. Kub bu sırayla v_1, v_2, v_3, v_4, v_5 və v_6 rəngli kvadratları ziyarət etməlidir.
Girişin sonu boşluqla ayrılmış iki sıfırdan ibarət bir sətirlə göstərilir.
Hər bir giriş məlumat dəsti üçün, əgər həll varsa, ən az addım sayını, əks halda "unreachable" (çatılmaz) çıxarın. Hər iki halda, hər bir giriş məlumat dəsti üçün bir sətirdə çap edin.
Nümunə 1