ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2140. BitMazeCraft

Ограничение времени: 3.0 секунды
Ограничение памяти: 256 МБ
Влад — очень ответственный работник. Только вот вместо работы он играет в BitMazeCraft. Но вместо режима выживания он любит проходить пользовательские карты. А это, как Вы догадываетесь, очень трудно. Особенно когда в кабинет к Владу постоянно заходят его коллеги.
Сегодня Влад проходит простую карту размера A × B × H, где H — высота. На этой карте персонажем нужно добраться от одного места до другого, не выходя за её границы. Карта состоит из кубов 1 × 1 × 1, каждый куб имеет координаты (x, y, z) и либо занят, либо свободен (1 ≤ xA, 1 ≤ yB, 1 ≤ zH). Влада немного смущает возможная проверка босса, поэтому он хочет пройти эту карту как можно быстрее. «Пройти карту» значит провести персонажа от начала до конца.
Будем говорить, что клетка находится над полом, если её координата z равна 1, или клетка под ней занята. Управление в BitMazeCraft очень простое: персонаж размера 1 × 1 × 1 всегда обязан стоять в пустой клетке и находиться над полом. Персонаж может выполнять всего четыре типа различных движений в трёхмерном пространстве, каждое из которых занимает одинаковое количество времени:
  • движение по горизонтали вдоль одной из осей координат в соседнюю клетку ((x, y, z){(x, y ± 1, z), (x± 1, y, z)}) при условии, что она свободна и находится над полом (такое движение называется walk)
  • движение по горизонтали вдоль одной из осей координат через одну соседнюю по горизонтали клетку ((x, y, z){(x, y ± 2, z), (x ± 2, y, z)}) при условии, что по направлению движения обе клетки свободны; клетка, над которой персонаж перемещается в середине пути ({(x, y ± 1, z−1), (x± 1, y, z−1)}), свободна (иначе персонаж запнётся); и клетка назначения находится над полом (такое движение называется jump)
  • спуск на один слой вниз с переходом в соседнюю по горизонтали клетку ((x, y, z){(x, y ± 1, z−1), (x± 1, y, z−1)}) при условии, что клетка назначения свободна и находится над полом; и клетка над ней также свободна (такое движение называется drop)
  • подъём на один слой вверх с переходом в соседнюю по горизонтали клетку ((x, y, z){(x, y ± 1, z+1), (x ± 1, y, z+1)}) при условии, что клетка, находящаяся над изначальной, свободна и находится в пределах карты; клетка назначения свободна и находится над полом (такое движение называется climb).
На самом деле Влад даже не уверен, возможно ли вообще пройти эту карту, поэтому он попросил Вас ответить, стоит ли ему проходить эту карту и, если её можно пройти, как её пройти быстрее всего.

Исходные данные

В первой строке вводятся три целых числа A, B, H — длина, ширина и высота карты (1 ≤ A, B, H ≤ 50). Далее даны H · A строк длины B, сгруппированных в H блоков по A строк.
Блоки описывают участки карты с фиксированной координатой z и даны снизу вверх, то есть в порядке увеличения координаты z. Каждая строка описывает участок внутри блока с фиксированной координатой x, строки внутри одного блока даны в порядке увеличения координаты x. Символы в строке описывают клетки и даны в порядке увеличения координаты y. Символ «#» (код 35) обозначает занятую клетку, символ «.» (код 46) обозначает пустую клетку.
В последних двух строках вводятся по три целых числа — координаты изначальной позиции персонажа xfrom, yfrom, zfrom и координаты назначения xto, yto, zto соответственно (1 ≤ xfrom, xtoA, 1 ≤ yfrom, ytoB, 1 ≤ zfrom, ztoH).
Гарантируется, что изначальная клетка и клетка назначения свободны и находятся над полом.

Результат

Если карту невозможно пройти, в единственной строке выведите «NO» (без кавычек).
В противном случае в первой строке выведите «YES» (без кавычек). Во второй строке выведите целое число N — минимальное возможное количество движений персонажа для прохождения карты. В следующих N строках выведите соответствующие движения персонажа в формате typei directioni, где typei — тип движения: «walk», «jump», «drop» или «climb» (без кавычек); directioni — направление движения «north», «east», «south» или «west» (без кавычек): north — переход из (x, y, z) в (xk, y, z'), east — из (x, y, z) в (x, y+k, z'), south — из (x, y, z) в (x+k, y, z') или west — из (x, y, z) в (x, yk, z'); где k равно 2 при jump и 1 в любом другом случае; z' равно z при walk и jump, z − 1 при drop и z + 1 при climb.
Если существует несколько оптимальных способов пройти карту, вы можете вывести любой из них.

Примеры

исходные данныерезультат
1 2 1
..
1 1 1
1 2 1
YES
1
walk east
3 4 2
.#..
....
.#..
....
....
....
1 1 1
3 4 1
YES
4
climb east
jump south
drop east
walk east
Автор задачи: Вадим Баринов