Задача 98716
|
Название задачи: Робот. |
 |
Условие
В исследовательской лаборатории фирмы Robots&Co разработали новую модель робота. Главной особенностью данной модели робота является то, что он работает по заранее заданной программе, в которой могут присутствовать команды: сделать шаг на Юг, на Север, на Восток или на Запад. Робот исполняет программу строго последовательно и, дойдя до конца программы, останавливается. Специалисты из Robots&Co заинтересовались вопросом, сколько существует различных программ, состоящих из K инструкций, таких, что робот, выйдя из начала координат, придет в точку с координатами (X, Y). Оси координат располагаются параллельно сторонам света, и единица измерения, соответствует одному шагу робота. Напишите программу, которая дает ответ на этот вопрос.Формат входных данных
Во входном файле находятся три числа K, X и Y (0 <= K <= 16, |X|, |Y| <= 16), разделенные пробелами.
Формат выходных данных
В выходной файл ваша программа должна поместить одно число — количество программ для робота.
Решение
В этой задаче мы сталкиваемся с функцией трех переменных: F(X, Y, Z) - показывает количество маршрутов длины Z, приводящих в клетку (X, Y). К сожалению, такая структура данных как
Array [-16..16, -16..16, 0..16] of LongInt;требует много памяти. Забудем пока об этой трудности и напишем рекурсивную часть. Для ответа на поставленный в задаче вопрос можно посчитать число маршрутов длины Z - 1 в четыре клетки, смежных с заданной, а результаты сложить, не забывая случаи клеток на границе. Граничными условиями будут F(X, Y, 0) = 0, если хотя бы одна из координат X или Y отлична от нуля, и F(0, 0, 0) = 1. Действительно, если робота не двигать, то он может оказаться только в начале координат. Теперь вспомним о проблеме хранения данных. Использованное нами решение, конечно, далеко не оптимальное (с точки зрения расходования памяти). Действительно, для вычислений в некий момент времени необходимы данные только за предыдущий, что же происходило ранее, нас не интересует - с этим мы уже справились. Значит, достаточно хранить только 2 квадратные матрицы размером 31, - одна несет данные в предыдущий момент времени, а вторая вычисляется для текущего с использованием первой матрицы. После окончания расчета данные первой уже не нужны, ей присваиваем значение второй матрицы, увеличиваем счетчик времени и т.д. Ясно, что такую идею можно реализовать только итеративно.
for z := 1 to k do
begin
Way2 := Way1;
for i := -16 to 16 do
for j := -16 to 16 do
begin
s := 0;
if i <> -16 then s := s + Way2[i - 1, j];
if i <> 16 then s := s + Way2[i + 1, j];
if j <> -16 then s := s + Way2[i, j - 1];
if j <> 16 then s := s + Way2[i, j + 1];
Way1[i, j] := s
end
end;
Интересно, что итеративное решение в некоторых случаях работает несколько дольше рекурсивного. Это становится понятным, если учесть, что в итеративной форме мы подсчитываем количества всевозможных маршрутов, а в рекурсивном делаем только то, что нас просят.
