Masala #0574

Xotira 16 MB Vaqt 1000 ms
14

Tap Away #1

Tap Away juda ajoyib o'yin bo'lib, uning qoidalari quyidagicha.

1. O'yin \(N \times M\) maydonda bo'lib o'tadi. 

2. Maydondagi katakchalarga Tepaga, Pastga, Chapga, O'nga belgilari o'rnatilgan. 

3. Siz istalgan belgili katakchaga bosish orqali uni jadvaldan chiqarib yuborishingiz mumkin. Lekin buning uchun katakchaning yo'nalishidagi yo'lda boshqa katakcha bo'lmasligi kerak. Eslatib o'tamiz yo'lida to'siq bo'lmagan katakchani jadvaldan chiqarib yuborish bu bitta harakat hisoblanadi.

4. O'yinnig asosiy maqsadi jadvaldagi barcha katakchalarni yo'q qilishdan iborat.


Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(M\) butun sonlari beriladi.  \(N=M=2\).
Keyingi \(N\) ta qatorning har birida \(M\) tadan belgi: U-tepaga, D-pastga, L-chapga, R-o'ngga.


Chiquvchi ma'lumotlar:

Barcha katakchalarni jadvaldan chiqarib yubirish uchun eng kamida nechta harakat qilish kerak. O'yinda barcha katakchalarni jadvaldan chiqarish mumkin deb hisoblansin.


Misollar
# input.txt output.txt
1
2 2
UU
DD
4
Izoh:

Bu masala test rejimida bo'lgani uchun \(N\) va \(M\) sonlariga faqat 2 natural soni qiymat sifatida tanlangan.
Asosiy masala esa "Tap Away #2" nomi bilan joylanadi