Всем, наверное, знакома проблема перемещения крупной мебели в комнате, в которой уже стоит другая мебель. А если она еще и прикручена, скажем, к полу? Но, если проблема даже решаема, хорошо бы при этом еще и потратить как можно меньше усилий
Итак, предположим, у нас есть план комнаты следующего вида:
B0011
B0000
B0000
11000
EEE00
Где 0 - свободное пространство, 1 - предметы, которые мы не можем передвигать, BBB - предмет мебели, скажем, диван, который мы должны переместить в место EEE. Начальное положение BBB и конечное - EEE может быть произвольным, но это всегда часть строки или столбца (линия) нечетной длины (естественно, количество E совпадает с количеством B).
Перемещать предмет мы можем, задавая следующие команды:
U - сдвинуть на клетку вверх.
D - сдвинуть на клетку вниз
R - сдвинуть на клетку вправо
L - сдвинуть на клетку влраво
T - развернуть вокруг центральной клетки
Передвигать диван мы можем только так, чтобы он не пересекался с другой мебелью. А разворачивать только тогда, когда квадрат со стороной равной длине дивана с центром в его середине пуст.
Например, на следующей картинке дан план части комнаты, где "?" обозначены места, на которых не должны стоять "1" для того, чтобы диван можно было повернуть.
000000
0?????
0?????
0BBBBB
0?????
0?????
Длина дивана - нечетное число 1<=k<20. Ваша задача - написать программу, которая по начальному плану комнаты будет определять как можно более короткую последовательность команд, которая будет перемещать диван из начальной позиции в конечную. Имя программы room.pas.
Входной файл room.dat содержит в первой строке длину стороны комнаты n<=50, комната представляет собой квадрат, далее план комнаты без пробелов.
Выходной файл room.sol содержит строку с количеством команд последовательности, которая перемещает диван из начального положения в конечное. Далее по одной команде на строку в порядке их выполнения. Если не существует способа доставить диван на место вывод должен содержать только 0.
