Рикошетные Роботы
Рикошетные Роботы
Бригада из четырех роботов будет доставить детали в производственный цех. Цех организован в виде прямоугольной сетки, в которой каждый робот занимает одну квадратную ячейку. Каждый робот представлен целым числом от 1 до 4 и может двигаться в четырех ортогональных направлениях (влево, вправо, вверх, вниз). Однако, однажды приведенный в движение, робот остановится только тогда, когда он обнаружит соседнее препятствие (например, стены, края фабрики или других неподвижных роботов). Роботы не движутся одновременно, то есть в каждый момент времени движется только один робот.
Цель состоит в том, чтобы вычислить эффективную последовательность движений, чтобы робот 1 достиг заданной цели; для этого возможно потребуется убрать с пути других роботов или использовать их в качестве препятствий для "рикошетных" движений.
Рассмотрим приведенный выше пример, где серые ячейки представляют стены, X - это целевое местоположение, а 1 и 2 обозначают начальные позиции двух роботов. Одно оптимальное решение состоит из шести ходов, описанных ниже.
Обратите внимание, что последовательность движений должна оставлять робота 1 в заданном месте, а не просто проходить через него (цель не заставляет роботов останавливаться - только стены, края и другие роботы).
Имея описание производственного плана, начальную позицию робота и целевую позицию, вычислите минимальное общее количество ходов, необходимое чтобы робот 1 достиг цели.
Входные данные
Первая строка содержит количество роботов n (1 ≤ n ≤ 4), ширину w и высоту h (w, h ≥ 1, max(w, h) ≤ 10) производственного этажа в ячейках, и верхний предел l (1 ≤ l ≤ 10) на количество ходов для поиска решений. Остальные h строк текста представляют собой строки производственного цеха с w символами, каждый из которых представляет позицию ячейки:
- W ячейка занятая стеной;
- X (одна) целевая ячейка;
- 1, 2, 3, 4 начальные позиции роботов;
- ’.’ пустая ячейка.
Выходные данные
Выведите минимальное количество ходов для робота 1, за которое можно достичь целевого местоположения, или NO SOLUTION если не существует решения с меньшим или равным заданному верхнему пределу количеством ходов.
2 5 4 10 .2... ...W. WWW.. .X.1.
6
1 5 4 10 ..... ...W. WWW.. .X.1.
NO SOLUTION