Masala #0986

Xotira 16 MB Vaqt 1000 ms
14

Labirintdagi sichqon

Sizga \(n\) soni va \(n\times n\) o`lchamli faqat \(0\) va \(1\) lardan tashkil topgan matritsa beriladi. Sichqon matritsaning \((1, 1)\) nuqtasidan \((n, n)\) nuqtasiga borishi kerak. Matritsadagi \(1\) bu yo`l bor degani \(0\) esa yo`l yo'q degani. Shichqon labirintdan chiqib ketishi uchun unga yo`l ko`rsating  \(U\)-yuqoriga, \(D\)-pastga, \(L\)-chapda, \(R\)-o'ngda. Shichqonga labirintdan chiqishiga ko`maklashing.
 


Kiruvchi ma'lumotlar:

Birinchi qatorda \(n(1\leq n\leq 5)\) natural son.
Ikkinchi qatorda \(0\) va \(1\) dan tashkil topgan \(n\times n\) matritsa kiritiladi


Chiquvchi ma'lumotlar:

Agar sichqonning labirintdan chiqish yo`llari bir nechta bo'lsa leksikografik jihatdan o'sish tartibida bitta satirda probil bilan ajratilgan holda chop eting, agar yo'l ma'vjud bo'lmasa \(-1\) ni chop eting.


Misollar
# input.txt output.txt
1
3
1 1 0
0 1 1
0 1 1
RDDR RDRD
2
3
1 1 0
0 1 0
1 0 1
-1