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