İlan oyunu#4971
İlanların labirintlərdə yaşaması çətin olduğu hər kəsə məlumdur. İlan tək olsa belə, divara və ya öz quyruğuna çırpılaraq ölə bilər. İlan yarışmasında qalib gəlmək istəyən Vasya, ilanını labirintin təhlükəli hissələrindən çıxmağı öyrətmək qərarına gəldi. Belə "alt-labirintlərin" təhlükəsi ondadır ki, ilan oradan sağ çıxmaqda çətinlik çəkir və ilan nə qədər uzundursa, sağ qalma şansı bir o qədər azalır. Vasya ilanı belə öyrədir: ilan gənc yaşda, uzunluğu 2 olduqda, Vasya ilanı təlim üçün təhlükəli labirintə buraxır; ilanın məqsədi oradan mümkün qədər tez çıxmaqdır. Əgər sağ qalarsa, uzunluğu 3 olduqda təlim eyni labirintdə təkrarlanır və bu proses ilan tamamilə uzun (uzunluğu 18) olana qədər və ya ölməyənə qədər davam edir.
Labirint W eni və H uzunluğu olan düzbucaqlı kimi təsəvvür edilə bilər, hər bir hüceyrəsi ya maneə 'X', ya da boş yer '.'dir. Labirint keçilməz daşlarla '*' əhatə olunub, labirintin sərhədində yerləşən girişə bitişik olan bir hüceyrə '#' istisna olmaqla. Məsələn, 4 uzunluğunda və 3 enində sadə bir labirint:
Uzunluğu L olan ilan L hüceyrədən ibarət ardıcıllıqdır. Hər bir hüceyrə ardıcıllıqda qonşu hüceyrələrlə tərəf üzrə bitişikdir. Ardıcıllıqda bütün hüceyrələr fərqlidir. İlan cari hərəkət istiqamətinə nisbətən üç istiqamətdə sürünə bilər: düz, sola və ya sağa. İlan bütün bədəni ilə eyni vaxtda sürünür və birinci hüceyrədən başqa hər bir hüceyrə əvvəlki yerini tutur. İlanın icazə verilən hərəkətlərinə nümunələr:
321. -> .321
321 -> .32
... ..1
12 -> 23
.3 1.
12 -> 23
43 14
İlan hər zaman vahidində dəqiq bir hüceyrə sürünür, əgər sürünəcək yeri yoxdursa, o, ölür.
Birinci sətirdə labirintin ölçüləri H və W (1 ≤ H ≤ 300, 1 ≤ W ≤ 30) verilir. İkinci sətirdə girişin koordinatları h_0 və w_0 verilir. Burada ya h_0 = 1, ya h_0 = H, ya w_0 = 1, ya da w_0 = W. Sonra H sətir boyunca W simvolu olan labirintin təsviri verilir, burada 'X' maneəni, '.' isə boş hüceyrəni göstərir. Zaman sayımı 0-dan başlayır; ilanın başlanğıc mövqeyi: baş (h_0, w_0) nöqtəsindədir, bədənin qalan hissəsi çöldədir. Zaman sayımı ilanın başı yenidən (h_0, w_0) hüceyrəsində olduqda bitir. Və bir də, labirint təlim olsa da, uzunluğu 18 olan heç bir ilan oradan sağ çıxa bilməz.
Çıxış 16 sətir olmalıdır, burada i-ci sətir ilanın uzunluğu i+1 olan labirintdən çıxmağı üçün ən yaxşı vaxtı göstərir, ya da əgər o, mütləq öləcəksə −1 göstərir.
Nümunə 1