Входной файл: robots.in Выходной файл: robots.out Время на тест: 2 секунды Ограничение на память: 64MB Тесты к задаче:Скачать
Вы являетесь счастливым обладателем двух роботов, которые расположены в двух разных прямоугольных лабиринтах. Квадраты с координатами (1, 1) расположены в верхних левых (северо-западных) углах лабиринтов. В лабиринте с номером i (i = 1, 2) находится Gi охранников (0 £ Gi £ 10), пытающихся поймать роботов. Для этого они патрулируют лабиринты вперед и назад по своему участку патрулирования, представляющему собой несколько последовательных клеток лабиринта на одной прямой. Ваша задача — определить последовательность команд, приводящую к выходу обоих роботов из лабиринтов без их поимки охранниками.
В начале каждой минуты обоим роботам посылается одна и та же команда, которая представляет собой одно из четырех направлений (север, юг, восток или запад). Получив команду, робот перемещается на одну клетку в указанном направлении. Если выполнение команды приводит к столкновению робота со стеной, то вместо выполнения этой команды робот в течение данной минуты остается на месте. Считается, что робот выходит из лабиринта, когда оказывается за его пределами. Выйдя из лабиринта, робот игнорирует все последующие команды.
Для каждого охранника в начальный момент известна его позиция в лабиринте и направление, в котором он начнет двигаться. В начале каждой минуты одновременно с роботами охранники перемещаются на одну клетку. Охранник движется вперед со скоростью одна клетка в минуту до тех пор, пока он не достигнет конца своего участка патрулирования (то есть пока он не сделает на одно перемещение меньше, чем число клеток в его участке патрулирования). По достижении этого момента, охранник мгновенно разворачивается и в дальнейшем продолжает движение в обратном направлении к своей начальной позиции. Достигнув начальной позиции, он снова разворачивается и повторяет свое движение по участку патрулирования до тех пор, пока оба робота не выйдут из лабиринтов.
Участки патрулирования охранников таковы, что они не проходят через стены и не выходят за пределы лабиринта. Участки патрулирования охранников могут пересекаться, однако никакие два охранника никогда не столкнутся, то есть они никогда не будут занимать одну и ту же позицию к концу одной и той же минуты. Охранники также не будут одновременно находиться в соседних клетках и двигаться настречу друг другу в течение этой минуты. Начальное положение охранника не будет совпадать с начальным положением робота.
Считается, что охранник поймал робота, если охранник и робот оказываются в одной и той же позиции к концу минуты, либо если охранник и робот находятся в соседних клетках и двигаются навстречу друг другу.
По заданному описанию двух лабиринтов (размер каждого из лабиринтов не больше 20x20), известным начальным позициям каждого из роботов и участкам патрулирования охранников определите последовательность команд, приводящую к выходу из лабиринтов обоих роботов без поимки их охранниками. При этом нужно минимизировать время, которое потребуется для того, чтобы оба робота вышли из лабиринтов. Если роботы выходят из лабиринтов в разные моменты времени, то время того робота, который вышел раньше, не существенно (учитывается лишь время того робота, который вышел позднее).
Входные данные: robots.in
Первая часть строк во входном файле описывает первый лабиринт и тех, кто в нем находится. Соответственно, вторая часть описывает второй лабиринт и тех, кто в нем находится.
Первая строка входного файла содержит два разделенных пробелами целых числа R1 и C1 — количества строк и столбцов в первом лабиринте соответственно.
В каждой из последующих R1 строк содержится по C1 символов, описывающих конфигурацию лабиринта. Начальное положение робота обозначается символом ‘X’. Символ ‘.’ обозначает пустую клетку, а символ ‘#’ — стену. В лабиринте всегда ровно один робот.
После описания лабиринта следует строка, содержащая единственное целое число G1 — количество охранников в первом лабиринте (0 £ G1 £ 10).
Каждая из последующих G1 строк описывает участок патрулирования охранника в виде трех целых чисел и символа, разделенных пробелами. Первое и второе числа указывают строку и столбец начального положения охранника. Третье число (2…4) представляет собой количество клеток в участке патрулирования данного охранника. Символ ‘N’, ‘S’, ‘E’ или ‘W’ (север, юг, восток и запад соответственно) указывает начальное направление движения охранника.
Описание второго лабиринта и тех, кто в нем находится, следует за описанием первого лабиринта в том же формате.
Если искомое решение существует, то первая строка выходного файла должна содержать единственное целое число K (K £ 10000) — количество команд для обоих роботов, приводящих к их выходу из лабиринтов без поимки охранниками. Гарантируется, что в этом случае кратчайшая последовательность команд имеет длину не больше 10000. В последующих K строках должны располагаться команды, каждая из которых представляет собой один из символов ‘N’, ‘S’, ‘E’ или ‘W’. Если решения не существует, то необходимо вывести единственную строку, содержащую “-1”.
После выполнения представленной последовательности команд оба робота должны оказаться за пределами лабиринтов. Последняя команда должна приводить к выходу из лабиринта хотя бы одного из роботов. Если существует несколько решений с минимальным временем, то любое из них считается правильным.
Пример выходных данных:
8
E
N
E
S
S
S
E
S
СИСТЕМА ОЦЕНКИ
В тех тестах, где решения не существует, будет оцениваться только правильный ответ. Частичные баллы за другие тесты будут начисляться следующим образом:
Корректность: 20% баллов
Выходной файл считается корректным, если он оформлен в соответствии с требованиями условия задачи, содержит не более 10000 команд и их последовательность приводит к выходу обоих роботов из лабиринтов. При этом последняя команда должна приводить к выходу хотя бы одного из роботов.
Минимальность: 80% баллов
Считается, что решение, представленное в выходном файле минимальное, если оно корректно и не существует более короткой последвательности команд, которая также корректна. Решение, в котором последовательность команд не минимальна, не получает баллов за минимальность.
FOTT - стильная одежда 2009 edwin jeans известные бренды по приемлемым ценам . система канализации септик . Качественный ремонт цифровых фотоаппаратов canon у метро . Студийные фотографы и свадебный фотограф - проведут съемку на венчание.