01. Лабиринт-1
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть робот, который находится в двумерном лабиринте из N × M клеток. Некоторые пары соседних по стороне клеток разделены стеной или дверью. Снаружи лабиринт со всех сторон окружен стенами. Некоторые клетки лабиринта являются выходами. Чтобы покинуть лабиринт, робот должен оказаться в любом из выходов. В некоторых клетках могут находиться ключи. Любой ключ может открыть любую дверь, но после открытия остается в замке. Таким образом, каждый ключ можно использовать лишь один раз. В лабиринте нет клеток содержащих и ключ, и выход. Также между парой соседних клеток не может находиться и стена и дверь.

Ваша задача написать программу на языке abc (описание языка находится ниже), которая приведёт робота к одному из выходов. Будем считать, что строки лабиринта пронумерованы от 0 до N - 1 сверху вниз, а столбцы – от 0 до M - 1 слева направо.

В языке abc доступны следующие базовые команды:

  • move-DIR – пройти в соседнюю клетку в направлении . down увеличивает номер строки на 1, right увеличивает номер столбца на 1. Если в данном направлении находится стена или закрытая дверь, ничего не происходит.
  • open-DIR – открыть дверь между текущей клеткой и соседней клеткой по направлению DIR. Если двери в этом направлении нет, или она уже открыта, или у робота нет ключа, ничего не происходит.
  • take – поднять ключ, находящийся в текущей клетке. Если в текущей клетке ключа не было или робот его уже поднял, то ничего не происходит. Робот может носить с собой произвольное количество ключей.
  • terminate – завершить программу. Эту команду вам не обязательно использовать. В случае её отсутствия команда добавится в конец программы автоматически.

Также в языке abc доступны управляющие команды:

  • for-N OPS end – повторяет последовательность команд OPS ровно N раз, 0 < N ≤ 100000. Каждая проверка счетчика цикла считается за выполненную роботом команду.
  • if-ok OPS1 else OPS2 endif – выполняет последовательность команд OPS1, если предыдущая команда движения, поднятия ключа или открытия двери была выполнена успешно, иначе выполняет последовательность команд OPS2. Если до этого не было выполнено ни одной перечисленной команды, то будет выполнена последовательность команд OPS1. Проверка if-ok считается за выполнение роботом команды.
  • break – останавливает текущий цикл for.
  • continue – заканчивает текущую итерацию цикла for.

Обратите внимание, что управляющие и базовые команды могут вкладываться друг в друга произвольным образом.

Робот будет выполнять ваши команды последовательно пока не выйдет из лабиринта, не закончатся команды, не будет выполнена команда terminate или не будет превышено допустимое количество выполненных команд 5·106.

В языке abc каждая команда является отдельным словом и должна быть отделена от других команд хотя бы одним пробельным символом.

Вам необходимо написать программу, которая выведет последовательность команд, выводящую робота из лабиринта. Разумеется вам как хорошему программисту нужно оптимизировать эти последовательности команд.

Количество непробельных символов в последовательности команд не должно превышать 107. За успешный выход из лабиринта i вам будет начислено количество очков равное:

где:
  • Wi – вес лабиринта, некоторая фиксированная для лабиринта константа.
  • Gi – количество передвижений робота.
  • Oi – общее количество выполненных роботом команд. Обратите внимание, что в это число входят, например, команды take, выполненные в клетках без ключа, а также команды открытия уже открытых дверей.
  • Li – длина последовательности команд в символах, исключая пробельные символы и переводы строк.
  • Q = 10·N·M.

В случае, если ваша последовательность команд не приведет робота к выходу вам будет начислено 0 очков. Результатом вашей программы будет являться сумма всех Si. Эту величину вам нужно максимизировать.

Все лабиринты вам будут известны и доступны. Вы можете скачать архив с лабиринтами с помощью любой из ссылок указанных ниже, пароль для разархивации aimtechiscool:

  1. https://drive.google.com/file/d/1dkIBfW_Gy6c3FJtXjMXZPMsGKRyn3pzp
  2. https://www.dropbox.com/s/77jrplnjgmviiwt/aimmaze.zip?dl=0
  3. https://yadi.sk/d/JNXDLeH63RzaCi

Для удобства локального тестирования ваших программ вам будет доступна программа подсчёта вашего результата (чекер), а также визуализации лабиринта. Эта программа написана на языке python3, поэтому вам понадобится интерпретатор языка python3, а также библиотека pillow, которую вы можете установить, выполнив команду pip3 install pillow. pip3 – это утилита для установки пакетов (библиотек) python3, она автоматически устанавливается вместе с интерпретатором python3.

Пример запуска чекера и визуализатора: python3 aimmaze.py maze.in robot.abc --image maze.png. Чекер возможно запустить без визуализации: python3 aimmaze.py maze.in robot.abc. Флаг --output-log позволит увидеть информацию о каждом шаге робота: python3 aimmaze.py maze.in robot.abc --output-log. Обратите внимание, что python3 мог установиться как просто python.

Для настроек изображения вы можете редактировать константы в начале программы aimmaze.py.

Входные данные

В первой строке заданы целые числа i,  W,  N,  M,  x0,  y0,  C,  D,  K,  E.

  • 1 ≤ i ≤ 14 – номер лабиринта (задан для удобства проверяющей программы).
  • 1 ≤ W ≤ 1018 – вес лабиринта (задан для удобства проверяющей программы).
  • 2 ≤ N, M ≤ 1000 – высота и ширина лабиринта.
  • 0 ≤ x0 ≤ N - 1,  0 ≤ y0 ≤ M - 1 – стартовая позиция робота (x0, y0).
  • 0 ≤ C ≤ 2·NM – количество стен.
  • 0 ≤ D ≤ 105 – количество дверей.
  • 0 ≤ K ≤ 105 – количество ключей.
  • 1 ≤ E ≤ 1000 – количество выходов.

Координата x соответствует номеру строки, y – номеру столбца. Точка (0, 0) находится слева сверху, так что направление down увеличивает координату x, а направление right увеличивает координату y.

В следующих C строках содержатся по 4 числа в каждой x1, y1, x2, y2 – координаты клеток в 0-индексации, между которыми есть стена. Гарантируется, что |x1 - x2| + |y1 - y2| = 1,  0 ≤ x1, x2 ≤ N - 1,  0 ≤ y1, y2 ≤ M - 1. Также по границам лабиринта всегда есть стены, которые не даны в описании лабиринта.

В следующих D строках содержится описание дверей в том же формате, что и стен. Гарантируется, что двери не накладываются на стены.

В следующих K строках находятся пары чисел – координаты ключей в 0-индексации.

В следующих E строках находятся пары чисел – координаты выходов в 0-индексации.

Гарантируется, что стартовая позиция, ключи и выходы находятся в попарно различных точках.

Выходные данные

Выведите программу на языке abc, которая проходит заданный лабиринт. Команды должны быть отделены друг от друга хотя бы одним пробельным символом. Форматирование программы не имеет значения.

Пример
Входные данные
1 1 30 30 1 1 1 1 1 1
1 1 1 2
2 2 2 3
1 4
9 0
Выходные данные
for-1111
  take
  open-up
  open-left
  open-right
  open-down
  move-left
  if-ok
    for-11
      move-left
  take
  open-up
  open-left
  open-right
  open-down
    end
  else
    move-right
    if-ok
      for-11
        move-right
  take
  open-up
  open-left
  open-right
  open-down
      end
    else endif
  endif

  move-up
  if-ok
    for-11
      move-up
  take
  open-up
  open-left
  open-right
  open-down
    end
  else
    move-down
    if-ok
      for-11
        move-down
  take
  open-up
  open-left
  open-right
  open-down
      end
    else endif
  endif

end