Miku-nun İlan Oyunu#12446
Miku klassik Snake oyununu oynayır.
Oyun sətir və sütundan ibarət düzbucaqlı lövhə üzərində oynanılır. İlan lövhənin bir neçə ardıcıl hüceyrəsindən ibarətdir. Hər addımda ilanın başı dörd qonşu hüceyrədən birinə hərəkət edir: yuxarı, aşağı, sola və ya sağa. Bundan sonra, ilanın hər bir digər hissəsi birbaşa onun qarşısında olan hissəni izləyir.
İlan lövhədən çıxa bilməz və bədəninin heç iki hissəsi eyni hüceyrəni tuta bilməz.
Miku lövhə üzərində mümkün olan ən böyük uzunluqda ilan yerləşdirmək istəyir ki, hərəkətə başladıqdan sonra o, sonsuzadək hərəkət edə bilsin.
Siz belə bir yerləşdirmənin istənilən birini çıxarmalısınız.
Yerləşdirmə sətir və sütundan ibarət cədvəl kimi təsvir olunmalıdır. Hər hüceyrədə beş simvoldan biri olmalıdır:
"L" — bu hüceyrə ilana aiddir və ilanın növbəti hissəsi soldakı qonşu hüceyrədə yerləşir;
"R" — bu hüceyrə ilana aiddir və ilanın növbəti hissəsi sağdakı qonşu hüceyrədə yerləşir;
"U" — bu hüceyrə ilana aiddir və ilanın növbəti hissəsi yuxarıdakı qonşu hüceyrədə yerləşir;
"D" — bu hüceyrə ilana aiddir və ilanın növbəti hissəsi aşağıdakı qonşu hüceyrədə yerləşir;
"." — bu hüceyrə ilana aid deyil.
Başqa sözlə, istənilən bir ilan hüceyrəsindən başlayıb cari hüceyrədə yazılmış simvola uyğun olaraq dəfələrlə hərəkət etsəniz, bütün ilan hüceyrələrini ziyarət etməli və başlanğıc hüceyrəyə qayıtmalısınız. Bunun sayəsində ilan sonsuzadək hərəkət edə biləcək.
Bundan əlavə, ilan dərhal gəldiyi hüceyrəyə geri qayıda bilməz. Formal olaraq, elə iki qonşu ilan hüceyrəsi və olmamalıdır ki, hüceyrəsindəki simvol hüceyrəsini göstərsin və hüceyrəsindəki simvol yenidən hüceyrəsini göstərsin.
Məsələn, birbaşa üstündə "U" olan "D" simvollu hüceyrə qadağandır. Eyni şəkildə, birbaşa solunda "L" olan "R" simvollu hüceyrə də qadağandır.
Əgər maksimum uzunluqlu bir neçə düzgün yerləşdirmə varsa, onların istənilən birini çıxarın.
Tək sətirdə iki tam ədəd və verilir (2 \le n, m \le 1000) — lövhənin ölçüləri.
Birinci sətirdə bir tam ədəd çıxarın — sonsuzadək hərəkət edə bilən ilan üçün yerləşdirilə bilən maksimum uzunluq.
Növbəti sətirdə hərəsində simvol çıxarın — ilanın yerləşdirilməsinin təsviri.
Qeyri-boş hüceyrələrin, yəni "L", "R", "U" və ya "D" simvolları olan hüceyrələrin sayı -ə bərabər olmalıdır.
Nümunə 1
Nümunə 2
Birinci nümunədə lövhənin ölçüsü 3 \times 5-dir. Hər iki ölçü tək olduğuna görə, ilan bütün hüceyrələri tuta bilməz. Optimal yerləşdirmələrdən birinin uzunluğu -dür.
Əgər hüceyrəsindən başlayıb oxları izləsəniz, ilan işğal olunmuş hüceyrənin hamısını ziyarət edəcək və hüceyrəsinə qayıdacaq, buna görə də o, sonsuzadək hərəkət edə bilər.
İkinci nümunədə lövhənin ölçüsü 4 \times 4-dür. Bu halda ilan bütün hüceyrəni tuta bilər.
Alt tapşırıq ( xal): və cütdür.
Alt tapşırıq ( xal): və -dən ən azı biri cütdür.
Alt tapşırıq ( xal): Əlavə məhdudiyyət yoxdur.