Pascal. Перемещение по графику.

[nobody_nohead]

Имеется олимпиадная задача:
График. Робот. Начальная позиция робота на графике - 0 0. Перемещаться он может во все стороны света на 1 за ход (Север, Юг, Запад, Восток). На вход поступает число от 0 до 16, показывающее количество ходов, и координаты конечной точки. Написать программу, вычисляющую сколько возможных путей может быть у робота из точки 0 0 до места назначения, с использованием заданного количества ходов. Ни больше, ни меньше. Пример: Input - 3 1 0
Output - 9
Код напишу сам, помогите с алгоритмом. Заранее спасибо.

[BDA]

Поскольку максимальное количество ходов ограничено 16, то проще всего рекурсивно в глубину перебрать все возможные пути. Кода получилось всего строчек 10.

[nobody_nohead]

Сообщение от BDA

проще всего рекурсивно в глубину перебрать все возможные пути

Чего - то я очень туплю, не подскажите как реализовать этот перебор? Вот что у меня получилось:

program olymp3;

var x, y, dif, n, i: integer;
    ans: longint;

begin
{Init data}
writeln('Input n, x, y: ');
read(n); read(x); read(y); 

{Solution}
if n < (x + y) then {Not enough turns to reach}
begin
	ans:= 0;
end
else if n = (x + y) then {Equal}
begin
	if x = 0 or y = 0 then
	begin
		ans:= 1;
	end
	else
	begin
		ans:= 2;
	end;
end
else {Counting}
begin
	dif:= n - (x + y);
	if (dif mod 2) = 1 then
	begin
		ans:= 0;
	end
	else
	begin
		{}
	end;	
	

end;

{Answer}
writeln(ans);
readln;
end.

[Serge_Bliznykov]

попробуйте так:

function Count(n, x, y, xk, yk : integer) : integer;
var Res : integer;
begin
  if n=0 then begin
    if (x=xk) and (y=yk) then Count := 1
    else Count := 0;
    Exit
  end;
  Count := Count(n-1, x+1, y, xk,yk) +
     Count(n-1, x-1, y, xk,yk) +
     Count(n-1, x, y+1, xk,yk) +
     Count(n-1, x, y-1, xk,yk);
end;

var n,x,y : integer;
begin
  n := 3;
  x := 1;
  y := 0;
  WriteLn('для n=',n,' и координат назначения ',x,y,
     ' существует ',Count(n,0,0,x,y),' способов')
end.

[BDA]

К ответу Serge_Bliznykov добавлю, что вы верно добавили проверку на количество необходимых шагов. Без этой проверки код ниже выполнялся примерно 13 секунд на случае 16 шагов, и 2 секунды - с проверкой:

function solve(step, x1, y1, x2, y2: integer): integer;
begin
  if step < abs(x1 - x2) + abs(y1 - y2) then
    result := 0
  else if step = 0 then
    result := ord((x1 = x2) and (y1 = y2))
  else
    result := solve(step - 1, x1, y1, x2 + 1, y2) + solve(step - 1, x1, y1, x2 - 1, y2) +
        solve(step - 1, x1, y1, x2, y2 + 1) + solve(step - 1, x1, y1, x2, y2 - 1);
end;
...
// вызов solve(step, x1, y1, 0, 0)

[nobody_nohead]

Сообщение от Serge_Bliznykov

попробуйте так:

Спасибо, работает.

[nobody_nohead]

Всем большое спасибо. Все оказалось куда тривиальнее, чем я думал.

[Serge_Bliznykov]

Сообщение от BDA

К ответу Serge_Bliznykov добавлю, что вы верно добавили проверку на количество необходимых шагов.

да, полностью согласен!