Quiz#4609
Demək olar ki, hər kəs uşaq oyunu olan "barley-break" (həmçinin sürüşkən tapmaca və ya 15-tapmaca kimi tanınır) ilə tanışdır. Bu məsələdə sizdən bu tapmacanın verilmiş vəziyyəti üçün bir həll tapmaq tələb olunur.
Oyun N \times N ölçülü kvadrat sahədən ibarətdir və sahə 1 \times 1 hüceyrələrə bölünüb. Hər hüceyrədə bir daş yerləşir, yalnız bir hüceyrə boşdur. Hər daş üzərində -dən N^2-1-ə qədər bir rəqəm yazılır. Hər rəqəm dəqiq bir dəfə qeyd olunur. Hər addımda siz boş hüceyrəyə bitişik olan bir daşı ona sürüşdürə bilərsiniz, beləliklə daşın əvvəlki yeri yeni boş hüceyrə olur. Daşlar sahədən kənara çıxa bilməz.
Tapmacanı həll etmək — daşları xüsusi şəkildə yerləşdirmək deməkdir:
Boş hüceyrə sonuncu sətrin sonuncu hüceyrəsində olmalıdır.
Klassik 15-tapmaca üçün bu şəkildə görünür:
Verilmiş vəziyyətdən başlayaraq, tapmacanın həllinə aparan (mütləq ən qısa olmayan, hətta boş ola bilən) bir hərəkətlər ardıcıllığı tapın. Əgər bu vəziyyətin həlli yoxdursa, "unsolvable" olduğunu çıxış edin.
Birinci sətirdə sahənin ölçüsü olan tam ədədi verilir. Sonrakı sətrin hər birində tam ədəd yazılmışdır. -dən N^2-1-ə qədər olan ədədlər daşları, isə boş hüceyrəni göstərir. Hər -dan N^2-1-ə qədər olan ədəd dəqiq bir dəfə iştirak edir.
Əgər ilkin vəziyyət həll olunmursa, **"No"** çap edin. Əks halda, ilk sətrdə **"Yes"**, ikinci sətrdə isə uyğun hərəkətlər ardıcıllığını (boşluqsuz) verin. Hərəkətlər belə kodlanır:
**'L'** — boş hüceyrənin solundakı daşı ora sürüşdürmək;
**'R'** — boş hüceyrənin sağındakı daşı ora sürüşdürmək;
**'U'** — boş hüceyrənin yuxarısındakı daşı ora sürüşdürmək;
**'D'** — boş hüceyrənin aşağısındakı daşı ora sürüşdürmək;
Hərəkətlərin sayı -dən çox olmamalıdır. Bir neçə həll mümkündürsə, istənilən birini çıxış edə bilərsiniz.
Qaydalar
2 \leq N \leq 50
0 \leq a_{ij} \leq N^2-1
Nümunə 1