Quiz
Каждый из вас скорее всего знаком с детской игрой "пятнашки". В этой задаче требуется найти решение для некоторой позиции.
Игра заключается в следующем: есть квадратное поле N×N, разбитое на клетки 1×1. Во всех клетках кроме одной есть фишки, на каждой из которых записано число от 1 до N^2-1. Каждое число встречается ровно один раз. На этом поле можно осуществлять ходы фишками, а именно, за один ход можно передвинуть одну из соседних с пустым местом фишек на это пустое место. При этом на месте фишки образуется пустое место. Фишки не могут покидать пределы поля.
Решить головоломку — значит расположить фишки в определенном порядке:
Пустое место должно оказаться в последней клетке последней строки.
Для обычных пятнашек это выглядит как:
Дана позиция, найти последовательность ходов (не обязательно кратчайшую, возможно пустую), которая её решает. Либо сказать, что позиция не имеет решения.
Входные данные
В первой строке число N — размер поля. Далее N строк по N чисел в каждой. Числа от 1 до N^2-1 соответствуют фишкам, 0 соответствует пустому месту. Каждое число от 0 до N^2-1 встречается ровно один раз.
Выходные данные
Если позиция не имеет решения, вывести "No". В противном случае в первой строке вывести "Yes", а во второй строку из ходов (без пробелов):
'L' - означает, что на пустое место надо передвинуть фишку, находящуюся слева от него.
'R' - означает, что на пустое место надо передвинуть фишку, находящуюся справа от него.
'U' - означает, что на пустое место надо передвинуть фишку, находящуюся сверху от него.
'D' - означает, что на пустое место надо передвинуть фишку, находящуюся снизу от него.
Количество ходов не должно превышать 2500000. Если решений несколько, можете вывести любое из них.
Ограничения
2 ≤ N ≤ 50
0 ≤ a_ij ≤ N^2-1