Задача g6_1040: Робот-сапер

Программа робота-сапера состоит из последовательности команд вида (a, b), где a - символ, принимающий значения W, N, O или S, что означает, соответственно, запад, север, восток или юг, а b - натуральное число, b < 20. Исполняя команду (a, b), робот делает шаг длины b в направлении a. Робот программируют и запускают из некоторой исходной точки на минное поле. Выполняя друг за другом команды программы, робот обезвреживает встречающиеся ему мины и после каждого шага сообщает, что соответствующая команда выполнена. Проторенная им тропа считается безопасной. Не поступление от робота очередного сообщения означает, что он все же подорвался. В этом случае на его замену из той же исходной точки запускают аналогичный робот. При программировании второго робота возникает следующая задача: найти такую последовательность команд, выполняя которую робот дойдет от исходной точки до места, из которого было получено последнее сообщение предыдущего робота; будет двигаться при этом только по участкам безопасной тропы; пройдет при этом путь минимальной длины.
Требуется написать программу, которая решает эту задачу.
Ввод данных организовать из файла input.txt или с клавиатуры, а вывод - в файл output.txt или на экран.

Формат входных данных:

1-я строка: K (K < 20) - количество команд, которые успел выполнить первый робот;
2-я строка: "a" "пробел" "b" - значения параметров 1-ой из этих команд;
3-я строка: "a" "пробел" "b" - значения параметров 2-ой из этих команд;
K+1-я строка: "a" "пробел" "b" - значения параметров K-ой из этих команд.

Формат выходных данных:

1-я строка: M - количество команд искомой последовательности;
2-я строка: "a" "пробел" "b" - значения параметров 1-ой из этих команд;
3-я строка: "a" "пробел" "b" - значения параметров 2-ой из этих команд;
M+1-я строка: "a" "пробел" "b" - значения параметров M-ой из этих команд.

Ограничение времени: 20 секунд.

Пример входных данных:

4
W 4
N 2
O 2
S 3

Пример выходных данных (соответствуют приведенным входным):

2
W 2
S 1

Решение g6_1040:
Что-то эта задачка у меня давно лежит решенная, а руки никак не дойдут разобрать. Ну что ж теперь настал и ее черед.
Во первых, надо завести массив 200*200 и закольцевать его (т.е. если вышли за левый край то переходим на правый) из элементов word или integer. Если у вас нет ограничений с памятью (например вы пишите на Free Pascal или на чем-нибудь подобном) заведите массив 400*400 и не закольцовывайте его. Такие размеры массивов объясняются тем, что в одном направлении робот может пройти не более 10 раз максимум по 20 клеток (если я правильно понял условие задачи). Заполним первоначально весь массив элементами 65536 или -1. Из точки (1; 1) начнем ползти соответственно инструкциям (N - вверх, S - вниз и т.д.) и заполнять все клетки, по которым проходит робот элементами 0.
Полностью выполнив все инструкции мы получим лабиринт, в котором клетки, по которым можно идти - нули, а заблокированные - не нули (логично). Для поиска кратчайшего пути в лабиринте необходимо употребить алгоритм заливки (он уже употреблялся ровно 10 задач назад, в задаче Лошадью ходи!(#1030)). Здесь мы пойдем от конечной точки во все стороны тем же самым нерекурсивным флудом. Область возможных значений здесь будет не все поле, а только небольшая (на первых шагах) часть, что позволит разогнать программу. Надо запомнить минимальную, максимальную, самую правую и левую координаты и, в случае, если мы вышли за эти границы, то их необходимо соответственным образом(с закольцованным массивом можно так не делать - замучаетесь, да и размер у него поменьше). Итак, в конечной клетке 0, затем проверяем четыре соседние клетки и в те, которые доступны ставим 1. Затем проверяем всю область на наличие 1 и т.д.
Как только мы нафлудим до начальной точки, то необходимо начать распутывать всю нашу конструкцию. Находим точку, на которую можно перейти с начальной точки (которая хранит значение X - общее количество шагов), и определяем в каком направлении надо двигаться. Двигаемся сколько можем (так чтобы координата следующей клетки в этом направлении была меньше на 1), считаем шаги. Как только придем к ситуации, что в этом направлении двигаться не можем, ищем новое доступное направление, выводим предыдущее направление и количество пройденных шагов. Вот если бы еще требывалось найти наименьшее количество команд с наименьшей длиной пути, то тогда пришлось писать перебор...