Всего несколько часов назад начался конкурс ICFPC-2012, который продлится все выходные. Я решил перевести задачу для этого конкурса в надежде, что кто-то из заинтересовавшихся людей успеет принять участие.
Задача вполне понятная, так что дерзайте.
Шахты с лямбдами обнаружены в Шотландии! Ваша задача — прочитав карту шахты суметь составить программу для робота.
Основные правила
- Робот пропускает любые неизвестные ему символы (а известны ему только L, R, U, D, W, A.
- Если Робот не может выполнить команду, он этот ход просто ничего не делает.
- После хода робота обновляется карта по правилам, описанным ниже.
- После обновления карты проверяются условия завершения работы.
Описание карты
Карта — это сетка m×n клеток, координата (1,1) расположена внизу и слева.
Каждая клетка содержит один из следующих символов:
- R — робот
- * — камень
- L — закрытый выход
- . — земля
- # — стена
- — λ
- O — открытый выход
- " " — пробел, пустая клетка
Ничто не может проникнуть сквозь стену. Ничто не может выйти за пределы поля m×n. Робот может копать землю, собирать λ и двигать камни. Камни падают. Камни могут убить робота.
Пример начального состояния:
#######
#..***#
#..\#
# ..**#
#.*.*#
LR....#
#######
Команды робота
Если координаты робота (x, y):
- L — налево, в (x-1, y)
- R — направо, в (x+1, y)
- U — вверх, в (x, y+1)
- D — вниз, в (x, y-1)
- W — ждать, ничего не делать
- A — прервать исследование шахты
Двигаться можно в клетку с открытым выходом, в пустую, в клетку с землёй и клетку с λ. Ещё можно двигаться (только налево и направо) в клетку с камнем, если за камнем пустое место. После ухода из клетки робот всегда оставляет в клетку пустоту.
Обновление карты (симуляция)
После движения робота проходит шаг симуляции. Во время этого этапа всегда читается старое состояние и пишется в новое. В следующем порядке по координатам: (1, 1), (2, 1), ..., (n, 1), (1, 2)… (n, m).
Правила проверяются по порядку, сверху вниз. Если одно сработало, то следующее уже не сработает.
- Под камнем пустота — камень падает на 1 клетку вниз.
- Под камнем — камень, справа пусто и справа внизу пусто — камень падает по диагонали вправо.
- Под камнем — камень, слева пусто и слева внизу пусто — камень падает по диагонали влево.
- Под камнем — λ, справа пусто и справа внизу пусто — камень падает по диагонали вправо.
- Остальные клетки не трогаются.
Если на карте больше нету λ, все закрытые выходы открываются.
Если под только что упавшим камнем стоял робот — робот ломается, это — поражение.
За один шаг симуляции камни падают на 1 клетку вниз.
Иногда камни с разных сторон могут упасть в одну клетку. В этом случае в этой клетке теперь лежит 1 камень.
Условия завершения
- Робот вошёл в открытый лифт — WIN
- Робот выполнил команду A — WIN
- Робота раздавило камнем — LOSE
Ввод/вывод
Ввод с stdin, вывод в stdout
Если некоторые строки короче максимальной по длине строки, то они считаются дополненными пробелами справа.
На каждой карте в начале нет открытых выходов. Есть ровно 1 робот и ровно 1 закрытый выход.
Карта может быть 1000×1000 и более.
Начисление очков
За каждый шаг -1
За собранную λ +25
За собранную λ в момент выполнения команды A +25
За собранную λ в момент достижения выхода +50
Скрипт для тестирования своих вариантов прохождения тестовых карт: validator
Лимиты
Программа должна работать на 32bit Debian-linux c 1 Gb RAM.
Через 150 секунд программа получает SIGINT, после этого у неё есть 10 секунд на вывод ответа.
После этих 10 секунд SIGKILL и 0 очков.
В течение конкурса будет от 1 до 4 изменений правил.
Детали на английском: icfpcontest2012.wordpress.com/
Автор: jerom
