Quiz#4609
Майже всі знають дитячу гру "п'ятнашки" (також відому як sliding puzzle або 15-пазл). У цій задачі вам потрібно знайти розв'язок для конкретної позиції цієї гри.
Гра складається з квадратного поля розміру N \times N, поділеного на клітини 1 \times 1. У кожній клітині знаходиться плитка, крім однієї. На кожній плитці написане число від до N^2-1. Кожне число зустрічається рівно один раз. За один хід можна пересунути плитку, яка знаходиться поруч із порожньою клітинкою, у цю клітинку, після чого порожньою стає клітинка, де раніше була плитка. Плитки не можна виносити за межі поля.
Розв'язати гру — означає розташувати плитки у визначеному порядку:
Порожня клітинка має знаходитись у останній клітинці останнього рядка.
Для класичної 15-пазл це виглядає так:
За заданою поточною позицією знайдіть послідовність ходів (не обов'язково найкоротшу, можливо порожню), яка веде до розв'язаної позиції. Якщо розв'язку не існує, виведіть повідомлення про невирішуваність позиції.
У першому рядку задано ціле число — розмір поля. У наступних рядках розміщено цілих чисел. Числа від до N^2-1 відповідають плиткам; позначає порожню клітинку. Кожне число від до N^2-1 зустрічається рівно один раз.
Якщо початкова позиція є невирішуваною, виведіть "No". Інакше виведіть у першому рядку "Yes", а у другому рядку — відповідну послідовність ходів (без пробілів). Кодування ходів таке:
'L' — пересунути плитку ліворуч від порожньої клітинки на її місце;
'R' — пересунути плитку праворуч від порожньої клітинки на її місце;
'U' — пересунути плитку що вище порожньої клітинки на її місце;
'D' — пересунути плитку що нижче порожньої клітинки на її місце.
Кількість ходів не повинна перевищувати . Якщо існує декілька рішень, ви можете вивести будь-яке з них.
Обмеження
2 \leq N \leq 50
0 \leq a_{ij} \leq N^2-1
Приклад 1