Labirint

Jerome K. Jerome-un "Üç nəfər qayıqda, itdən başqa" əsərinin qəhrəmanı Harrisə Hampton Court labirintindən çıxmağa kömək edəcək bir proqram yazın. Labirint qərbdən şərqə və ya şimaldan cənuba uzanan düzbucaqlı bir sahədir. Onun ölçüləri yardlarla verilmişdir (təxminən 91,44 sm) və paralel və meridian boyunca müvafiq olaraq n və m natural ədədləri ilə ifadə olunur. Ümumi sahəsi mn 10000 (kvadrat yard) keçmir. Labirint, hər biri 1 yard tərəfi olan kvadratlara bölünmüşdür. Bu kvadratların bəziləri yalnız yan keçilə bilən tikanlı kollarla örtülmüşdür.

Giriş məlumatları

Birinci sətir labirintin yardlarla ölçülərini göstərən iki natural ədəd m və n ehtiva edir. Sonrakı m sətir n simvoldan ibarət olub, labirintin sxemini göstərir. Burada " " (boşluq) simvolu boş kvadratı, "U" simvolu kol olan kvadratı, üstəgəl işarəsi "+" isə Harrisin başlanğıc yerini göstərir. Labirintdən çıxış 1-ci və m-ci sətirlərin elementləri və hər sətirin 1-ci və n-ci elementləri ilə mümkündür, əgər onlar boşluq və ya üstəgəl işarəsidirsə. Hərəkət kollarla örtülməmiş qonşu kvadrata dünya istiqamətləri üzrə edilir. Şimala, cənuba, qərbə və ya şərqə hərəkət sxemdə bir simvol yuxarı, aşağı, sola və ya sağa hərəkətə uyğun gəlir.

Çıxış məlumatları

Birinci sətir Harrisin labirintdən çıxması üçün atmalı olduğu ən azı 1 yard uzunluğunda addımların sayını göstərən tam ədəd olmalıdır.

İkinci sətir bu ən qısa yolun təsvirini ehtiva etməlidir - ilk addımdan sonuncuya qədər addımlar, burada n hərfi şimala (north), s cənuba (south), e şərqə (east), w qərbə (west) addımını göstərir.

Əgər Harris artıq çıxışdadırsa, birinci sətir yalnız 0 rəqəmini ehtiva edir və ikinci sətir boş qalır.

Əgər labirintdən çıxmaq mümkün deyilsə (bu halda Harris labirintin müvafiq yerinə necə düşdüyünü müzakirə etməyəcəyik), yeganə sətir yalnız -1 rəqəmini ehtiva etməlidir.