Рикошетні Роботи#7916
Бригада з чотирьох роботів доставляє деталі у виробничий цех, організований у вигляді прямокутної сітки. Кожен робот займає одну квадратну клітинку і позначений числом від 1 до 4. Роботи можуть рухатися в чотирьох напрямках: вліво, вправо, вгору або вниз. Однак, як тільки робот починає рух, він зупиняється лише тоді, коли зустрічає перешкоду (наприклад, стіну, край фабрики або іншого нерухомого робота). Роботи рухаються по черзі, тобто в кожен момент часу рухається лише один робот.
Завдання полягає в тому, щоб знайти ефективну послідовність рухів, щоб робот 1 досягнув заданої цілі. Для цього може знадобитися переміщення інших роботів з його шляху або використання їх як перешкод для "рикошетних" рухів.
На прикладі вище, сірі клітинки представляють стіни, X - цільове місце, а 1 і 2 - початкові позиції двох роботів. Одне з оптимальних рішень складається з шести ходів, як показано нижче.
Важливо, щоб робот 1 залишився на цільовій клітинці, а не просто пройшов через неї (ціль не змушує роботів зупинятися - лише стіни, краї та інші роботи).
Вам надано опис виробничого плану, початкову позицію робота і цільову позицію. Потрібно обчислити мінімальну кількість ходів, необхідну, щоб робот 1 досяг цілі.
Перший рядок містить кількість роботів (1 \le n \le 4), ширину і висоту (, h \ge 1, \max(w, h) \le 10) виробничого поверху в клітинках, і верхню межу (1 \le l \le 10) на кількість ходів для пошуку рішень. Наступні рядків представляють рядки виробничого цеху з символами, кожен з яких описує позицію клітинки:
W - клітинка зайнята стіною;
X - цільова клітинка (одна);
1, 2, 3, 4 - початкові позиції роботів;
'.' - порожня клітинка.
Виведіть мінімальну кількість ходів, за яку робот 1 може досягти цільового місця, або NO SOLUTION, якщо не існує рішення з кількістю ходів, меншою або рівною заданій верхній межі.
Приклад 1
Приклад 2