Masala #E

Xotira 16 MB Vaqt 1000 ms
14
Muallif: Ds_FoRResT

Tap Away #2

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

1. O'yin N×M maydonda bo'lib o'tadi. 

2. Maydondagi katakchalarga Tepaga, Pastga, Chapga, O'nga yo'nalishlari o'rnatilgan. Agar siz biron katakcha ustiga bossangiz va katakcha yo'nalishi bo'yicha yo'lakda bironta ham belgi bo'lmasa, katakcha o'ziga o'rnatilgan yo'nalish bo'yicha harakat qiladi, aks holda katakcha qimirlamaydi.

3. Siz istalgan 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.

Siz jadvaldagi barcha katakchalarni o'yindan chiqarib yuborish uchun eng kamida nechta harakat qilish kerakligini toping.


Kiruvchi ma'lumotlar:

Birinchi qatorda N va M butun sonlari beriladi.  ( 1 <= N,M <= 6)
Keyingi N ta qatorning har birida M tadan belgi probel bilan ajratilgan holda berilari: U-tepaga, D-pastga, L-chapga, R-o'ngga.


Chiquvchi ma'lumotlar:

Barcha katakchalarni jadvaldan chiqarib yuborish uchun eng kamida nechta harakat qilish kerak. Agar buning imkoni bo'lmasa -1 chiqaring.


Misollar
# input.txt output.txt
1
2 2
U D 
L R
4
2
2 2
U D 
R L
-1
Izoh:

1-test uchun na'muna:

          

Robocontest.uz Copyrighted © 2020-2022 by Robocontest Team

Generated in 26ms