Kaeru Tullanış
Böyük bir göldə yaşayan bir qurbağa var. O, göldə üzən lotus yarpaqları arasında tullanmağı çox sevir. Maraqlıdır ki, bu yarpaqlar qəribə vərdişlərə malikdir. Birincisi, qurbağa ondan tullandıqdan sonra yarpaq suya batacaq. İkincisi, onlar aşağıdakı nümunədə olduğu kimi, sanki şəbəkə nöqtələrinə yerləşdirilmiş kimi müntəzəm düzülmüşdür.
Şəkil 1: Üzən yarpaqların nümunəsi
Son zamanlar, o, bu vərdişlərdən istifadə edərək bir tapmaca oyunu icad etdi. Oyunun əvvəlində o, hansısa yarpağın üstündədir və yuxarı, aşağı, sola və ya sağa baxır. O, irəli və ya baxdığı istiqamətə nisbətən sola və ya sağa tullanmağı bacarır, amma geri və ya diaqonal tullanmaq olmaz. Məsələn, əgər o, sola baxırsa, o, sola, yuxarı və aşağı tullanmağı bacarır, amma sağa tullanmaq olmaz. Hər tullanışda, o, tullanma istiqamətində ən yaxın yarpağın üzərinə enəcək və əvvəlki vəziyyətindən asılı olmayaraq həmin istiqamətə baxacaq. Tullandığı yarpaq sudan yox olacaq. Bu tapmacanın məqsədi, yalnız bir yarpaq qalanadək yarpaqdan yarpağa tullanmaqdır.
Aşağıdakı şəkildə göstərilən nümunəyə baxın.
Bu vəziyyətdə, onun üç seçimi var: A, B və C yarpaqları. Qeyd edək ki, o, D yarpağına tullanmağı bacarmır, çünki geri tullanmaq olmaz. Tutaq ki, o, B yarpağını seçir. Oraya tullandıqdan sonra vəziyyət aşağıdakı şəkildə dəyişəcək.
O, növbəti dəfə ya E, ya da F yarpağına tullanmağı bacarır.
Bir neçə çətinlikdən sonra, o, bu tapmacanın çətin olduğunu başa düşdü, çünki göldə çoxlu yarpaq var. Ona həll yolu tapmaqda kömək edə bilərsinizmi?
Giriş verilənləri
H W c_{1,1} ... c_{1,W} ... c_{H,1} ... c_{H,W}
Girişin ilk sətri iki müsbət tam ədəd H və W (1 ≤ H, W ≤ 10) ehtiva edir. Sonrakı H sətirlər, hər biri W simvoldan ibarət olan, yarpaqların və qurbağanın ilkin konfiqurasiyasını aşağıdakı simvollarla təsvir edir:
'.' : su
'o' : yarpaq
'U' : yarpağın üstündə yuxarıya (yəni yuxarı tərəfə) baxan qurbağa
'D' : yarpağın üstündə aşağıya (yəni aşağı tərəfə) baxan qurbağa
'L' : yarpağın üstündə sola (yəni sol tərəfə) baxan qurbağa
'R' : yarpağın üstündə sağa (yəni sağ tərəfə) baxan qurbağa
Hər bir girişdə yalnız bir qurbağanın olduğunu qəbul edə bilərsiniz. Həmçinin, yarpaqların ümumi sayının (qurbağanın əvvəlcə olduğu yarpaq daxil olmaqla) ən çox 30 olduğunu qəbul edə bilərsiniz.
Çıxış verilənləri
Hərəkətlərin ardıcıllığını təsvir edən 'U' (yuxarı), 'D' (aşağı), 'L' (sol) və 'R' (sağ) simvollarından ibarət bir sətir çıxarın. Çıxışda boşluqlar kimi digər simvollar olmamalıdır. Hər bir giriş üçün yalnız bir həllin olduğunu qəbul edə bilərsiniz.