Магический квадрат
Числа от 1 до 9 записаны в квадрате 3x3 в произвольном порядке. Разрешается совершить циклический сдвиг на один элемент в некоторой строке (влево или вправо) или столбце (вверх или вниз). Напишите программу, которая за наименьшее количество таких операций преобразует квадрат в магический.
Рассмотрим пример таких преобразований:
Входные данные
Входные данные состоят из трех строк. Каждая строка содержит ряд квадрата - три числа, разделенных пробелами.
Отметим, что любой квадрат можно сделать магическим при помощи некоторого количества циклических сдвигов.
Выходные данные
Первая строка содержит целое число n – минимальное количество циклических операций, необходимых для преобразования входного квадрата в магический. За первой строкой следуют n строк, каждая из которых описывает один сдвиг. Сдвиги кодируются следующим образом:
Dx – сдвиг вниз столбца x;
Ux – сдвиг вверх столбца x;
Lx – сдвиг влево строки x;
Rx – сдвиг вправо строки x.
Номер строки (столбца) x (1 ≤ x ≤ 3) пишется после символов "D", "U", "L" и "R" без пробела. Строки квадрата нумеруются сверху вниз, столбцы слева направо.