Сокобан
Соко-бан — это японское слово, обозначающее работника склада, а также название классической компьютерной игры, созданной в 1980-х годах. Это игра для одного игрока, в которой работник находится в закрытом складе с одним или несколькими ящиками. Цель игры — переместить все ящики на целевые места, количество которых равно количеству ящиков. Игрок управляет движением работника с помощью клавиш со стрелками (вверх, вниз, влево, вправо) в соответствии со следующими правилами:
Если направление движения ведет работника на пустое место (т.е. там нет ящика или стены), работник перемещается на одну клетку в этом направлении.
Если направление движения ведет работника к ящику, и клетка за ящиком пуста, то и работник, и ящик перемещаются на одну клетку в этом направлении (т.е. работник толкает ящик).
Если направление движения ведет работника к стене или к ящику, за которым находится другой ящик или стена, движение не происходит.
Цель игры — разместить все ящики на целевых местах. Когда это происходит, игрок выигрывает (и все последующие нажатия клавиш игнорируются).
Игра была предметом изучения учеными в области компьютерных наук (один аспирант даже посвятил всю свою докторскую диссертацию анализу сокобана). К сожалению, нахождение решения в общем случае очень сложно, так как это задача как NP-трудная, так и PSPACE-полная. Поэтому ваша задача будет проще: симулировать ход игры на основе последовательности нажатий клавиш игрока. Для ввода и вывода состояние игры описывается с использованием следующих символов:
Например, начальная конфигурация, изображенная в начале этой задачи, представлена как первый входной случай ниже.
Входные данные
R
C
R
C
R
R
C
U
D
L
R
0 0
Каждая игра начинается со строки, содержащей целые числа и , где 4 ≤ ≤ 15 — количество строк, а 4 ≤ ≤ 15 — количество столбцов. Далее следуют строки, представляющие строки сверху вниз, причем каждая строка содержит ровно символов, слева направо. Наконец, есть строка, содержащая не более 50 символов, описывающая последовательность нажатий клавиш игрока, используя символы , , , и соответственно для вверх, вниз, влево и вправо. Вы должны прочитать всю эту последовательность из ввода, даже если конкретная игра может успешно завершиться до конца последовательности. Набор данных заканчивается строкой .
Мы гарантируем, что в каждой игре есть ровно один работник, равное количество ящиков и целевых мест, по крайней мере один изначально неправильно размещенный ящик и внешняя граница, состоящая полностью из стен.
Выходные данные
complete
incomplete
Для каждой игры вы должны сначала вывести строку, идентифицирующую номер игры, начиная с 1, и либо слово , либо , обозначающее, завершил ли игрок успешно эту игру. После этого должна следовать представление окончательной конфигурации доски.