Çəyirtkə#6917
Biz əyləncə parkındayıq və burada "Çəyirtkə Labirinti" adlanan bir sıra tramplinlər diqqətimizi çəkir. Aşağıdakı şəkildə göstərildiyi kimi, onların hamısı qeyri-mənfi tam ədədlərlə işarələnmişdir:
İnsanlar içəridə, bir tramplindən digərinə tullanaraq, cazibənin çıxışının yerləşdiyi şimal-qərb küncündəki tramplinə çatmağa çalışırlar. Əgər çıxışa kifayət qədər tez çatsanız, mükafat qazana bilərsiniz. Lakin mükafata uyğun olmaq üçün aşağıdakı qaydaya əməl etməlisiniz: z ilə işarələnmiş tramplindən tullandıqdan sonra, eyni sırada və ya sütunda z tramplin uzaqlığında olan digərinə keçməlisiniz.
Buna görə, probleminiz hər hansı bir tramplindən çıxış yoluna qədər olan ən qısa yolu tapmaqdır, tullanmaların sayı ilə ölçülür. Hər hansı bir tramplindən tullanmaların uzunluğu verildiyi üçün, hər tramplini üzərindəki ən yaxşı tullanmaların istiqaməti ilə işarələmək kifayətdir.
Verilən başlanğıc mövqeyindən bir yol digərindən daha qısa hesab olunur, əgər daha az tullanmalar tələb edirsə; bərabərlik halında, ilk addımda sizi cərgədə ən şimala aparan yol üstünlük təşkil edir; və yenə bərabərlik halında, sizi ən qərbə aparan yol üstünlük təşkil edir.
Bu simvollar əvəzinə, biz sadə mətn simvollarından istifadə edirik: oxlar üçün uyğun kardinal nöqtə ('N', 'S', 'E' və ya 'W'), mümkün qaçış olmayan tramplinlər üçün 'X' və yuxarı sol mövqedəki xüsusi tramplin üçün ulduz '*', bu da çıxışı təmsil edir.
Bir neçə hal tək bir test faylında verilir. Hər test halının ilk sətri arasında tək boşluq ilə ayrılmış 1 ilə 50 arasında olan iki tam ədəd ehtiva edir; birincisi matrisdəki sətirlərin sayı, ikincisi isə sütunların sayıdır. Sonra, matrisdəki elementlər ardıcıl olaraq, hər biri yenə tək boşluq simvolları ilə ayrılmış qeyri-mənfi tam ədəd olmaqla, sətir-sətir gəlir. 0×0 matrisi test hallarının sonunu bildirəcək və buna görə də analiz edilməməlidir.
Hər məlumat halının gözlənilən çıxışı simvol matrisidir. Hər element yuxarıda təsvir edildiyi kimi icazə verilən simvol dəstindən biri olan "N", "S", "E", "W", "X" və ya "*" olacaq. Hər halın çıxışı boş bir sətir ilə izlənilir.
Nümunə 1