Сокобан#3111
Соко-бан — це японське слово, що означає працівника складу, а також назву класичної комп'ютерної гри, створеної у 1980-х роках. Це однокористувацька гра з такою передумовою: працівник перебуває у закритому складі з однією чи кількома коробками. Мета полягає в тому, щоб перемістити ці коробки у певні цільові позиції, причому кількість цільових позицій дорівнює кількості коробок. Гравець задає напрям руху працівника за допомогою клавіш зі стрілками (вгору, вниз, вліво, вправо) згідно з такими правилами:
Якщо вказаний напрям руху працівника веде на порожню клітинку (тобто таку, де немає ні коробки, ні стіни), працівник пересувається на одну позицію в цьому напрямку.
Якщо вказаний напрям руху призводить до того, що працівник піде на клітинку з коробкою, і клітинка по інший бік коробки порожня, тоді і працівник, і коробка пересуваються на одну клітинку в цьому напрямку (тобто працівник штовхає коробку).
Якщо вказаний напрям руху призводить до того, що працівник натрапить на стіну або спробує зайти в коробку, по інший бік якої також коробка або стіна, рух не відбудеться під час цього натискання клавіші.
Метою є розмістити всі коробки одночасно на цільових позиціях. У такому випадку гравець досягає успіху (і, формально, усі наступні натискання клавіш ігноруються).
Гру досліджували комп'ютерні науковці (один аспірант навіть написав цілу дисертацію, присвячену аналізу соко-бану). На жаль, знаходження розв'язку взагалі є дуже складним, бо задача і NP-складна, і PSPACE-повна. Тому ваше завдання простіше: симулювати хід гри за послідовністю натискань клавіш гравцем. Для введення та виведення стан гри описується за такими символами:
Наприклад, початкова конфігурація, показана на початку задачі, представлена нижче як перший вхідний випадок.
Кожна гра починається з рядка, що містить цілі числа і , де 4 \le R \le 15 — кількість рядків, а 4 \le C \le 15 — кількість стовпчиків. Далі йдуть рядків, які представляють рядки згори донизу, кожен рядок містить рівно символів зліва направо. Нарешті, дається рядок, що містить не більше символів, який описує послідовність натискань клавіш гравцем за допомогою символів , , та для руху вгору, вниз, вліво і вправо відповідно. Ви повинні прочитати всю послідовність, навіть якщо гру можна завершити до її кінця. Набір даних закінчується рядком .
Гарантується, що у кожній грі є рівно один працівник, однакова кількість коробок і цільових позицій, принаймні одна коробка спочатку стоїть не на цільовому місці, а зовнішня межа повністю складається зі стін.
Для кожної гри спочатку виведіть рядок із номером гри, починаючи з , та словом complete або incomplete, що вказує, чи успішно гравець завершив цю гру. Далі виведіть зображення фінальної конфігурації ігрового поля.
Приклад 1