Задача C. Суперагент ≡

Условие

Женя Борин учится в школе юных суперагентов. На занятии по избавлению от слежки Борин получил такое теоретическое задание:

Зал аэропорта на плане имеет вид прямоугольника шириной W и высотой H метров. Пол разделён на клетки размером 1 × 1 метр. Клетка в северо-западном углу имеет координаты (1, 1).

На западной и северной стене через каждые два метра укреплены видеокамеры, обозревающие горизонтальную или вертикальную полосу шириной в одну клетку до противоположной стены. Таким образом, клетки, хотя бы одна координата которых чётна, просматриваются видеокамерами. Если агент попадёт в поле зрения камеры, поднимется тревога.

В зале находится N пассажиров. Пассажиры двигаются по залу, перемещаясь за 1 секунду на одну клетку по горизонтали или вертикали. Если между камерой и агентом есть хотя бы один пассажир, то агент остаётся незамеченным этой камерой.

Агент находится в точке с координатами (1, y_a) и желает попасть в точку с координатами (W, y_a), не подняв тревоги и затратив не более T секунд. Требуется написать программу, которая определит необходимую последовательность перемещений агента по известным координатам и перемещениям пассажиров.

Произвольное количество пассажиров может находиться одновременно в одной клетке, однако агент не может находиться в одной клетке с пассажиром.

Формат входного файла

Первая строка входного файла содержит числа W H T y_a N. Следующие N строк содержат значения x_i y_i p_i, где x_i, y_i — координаты i-го пассажира в начальный момент времени, p_i — строка из T символов, описывающая перемещения пассажиров в течении T секунд. Каждый символ равен "n", если пассажир перемещается на север, "s" — на юг, "w" — на запад, "e" — на восток, "z" — стоит на месте.

Формат выходного файла

Выходной файл должен содержать строку длиной не более T символов, описывающую движение агента в том же формате, что и движения пассажиров, либо строку IMPOSSIBLE, если решения не существует. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ W, H, T, N ≤ 100, y_a и W — нечётные, 1 ≤ x_i ≤ W, 1 ≤ y_i, y_a ≤ H

Примеры тестов

7 6 20 3 2
2 1 eeeeewwwwwweeeeeewww
3 2 ssssnnnnnsssssnnnnns

zzzzzzzzzzzeeeeee

3 4 5 3 1
1 1 zzzzz

IMPOSSIBLE

Разбор

Состояние суперагента можно описать двумя координатами и временем: (x; y; t). Из каждого состояния агент может перейти не более чем в пять других: (x + 1; y; t + 1), (x; y + 1; t + 1), (x − 1; y; t + 1), (x; y − 1; t + 1), (x; y; t + 1), соответствующим одному из четырех возможных перемещений или стоянию на месте. При этом, в некоторые состояния переходы запрещены, поскольку они соответствуют или выходу за пределы зала, или такому положению агента, что он окажется раскрыт (будет существовать камера, от которой агент не закрыт пассажиром).

Для решения задачи воспользуемся методом поиска в ширину. Пусть в трехмерном массиве a в элементе a[x][y][t] хранится длина кратчайшего пути от начального состояния (0; y_a; 0) до состояния (x; y; t), либо T + 1, если состояние недостижимо.

Изначально пометим все состояния как недостижимые и лишь для начального состояния запишем a[0][y_a][0] = 0. После этого будем перебирать все состояния в порядке возрастания t и изменять массив a для всех возможных переходов, то есть вычислять a[x + dx][y + dy][t + 1] = min(a[x + dx][y + dy][t + 1], a[x][y][t] + 1). Очевидно, что поскольку состояния перебираются в порядке возрастания времени, то на момент, когда рассматривается состояние (x; y; t), все состояния из которых можно было в него перейти уже были рассмотрены, а значит a[x][y][t] содержит длину минимального пути (строгое доказательство проводится методом полной математической индукции). Таким образом, после завершения перебора состояний ответом будет минимальное из чисел a[W][y_a][t], где t = 0… T.

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

Оценим вычислительную сложность алгоритма. В начале необходимо для каждого состояния определить, возможен ли переход в него. Предлагается для каждого момента времени вычислить позиции всех пассажиров и для каждого пассажира пометить клетки, которые он закрывает. Это может быть сделано за O(TN(W + H)). Всего имеется WH(T + 1) состояний, и O(1) (не более 5) переходов из каждого. Для формирования строки с ответом требуется линейное количество операций. Итак, временная сложность алгоритма может быть оценена как O(TN(W + H) + WHT) = O(T(NW + NH + WH)).