Quiz
Hər biriniz yəqin ki, uşaq oyunu "on beşlik" ilə tanışsınız. Bu tapşırıqda müəyyən bir vəziyyət üçün həll tapmaq lazımdır.
Oyun belədir: N×N ölçüsündə bir kvadrat sahə var, 1×1 ölçülü hüceyrələrə bölünmüşdür. Bütün hüceyrələrdə birindən başqa fişlər var, hər birində 1 ilə N^2-1 arasında bir rəqəm yazılmışdır. Hər bir rəqəm dəqiq bir dəfə rast gəlinir. Bu sahədə fişlərlə gedişlər etmək olar, yəni bir gedişdə boş yerin yanında olan fişlərdən birini bu boş yerə köçürmək olar. Bu zaman fişin yerində boş yer yaranır. Fişlər sahənin sərhədlərini tərk edə bilməz.
Bulmacanı həll etmək — fişləri müəyyən bir qaydada yerləşdirmək deməkdir:
Boş yer sonuncu sıranın sonuncu hüceyrəsində olmalıdır.
Adi on beşliklər üçün bu belə görünür:
Vəziyyət verilir, onu həll edən gedişlər ardıcıllığını tapmaq lazımdır (mütləq ən qısa olmamalıdır, bəlkə də boş ola bilər), ya da vəziyyətin həlli olmadığını bildirmək.
Giriş verilənləri
Birinci sətirdə N — sahənin ölçüsü. Sonra N sətir, hər birində N rəqəm. 1 ilə N^2-1 arasındakı rəqəmlər fişlərə uyğundur, 0 boş yerə uyğundur. Hər bir rəqəm 0 ilə N^2-1 arasında dəqiq bir dəfə rast gəlinir.
Çıxış verilənləri
Əgər vəziyyətin həlli yoxdursa, "No" çıxarın. Əks halda, birinci sətirdə "Yes", ikinci sətirdə isə gedişlər ardıcıllığını (boşluqsuz) çıxarın:
'L' - boş yerə onun solunda olan fişi köçürmək lazımdır.
'R' - boş yerə onun sağında olan fişi köçürmək lazımdır.
'U' - boş yerə onun üstündə olan fişi köçürmək lazımdır.
'D' - boş yerə onun altında olan fişi köçürmək lazımdır.
Gedişlərin sayı 2500000-dən çox olmamalıdır. Əgər bir neçə həll varsa, onlardan istənilən birini çıxara bilərsiniz.
Məhdudiyyətlər
2 ≤ N ≤ 50
0 ≤ a_ij ≤ N^2-1