Определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол - Free Pascal

Формулировка задачи:

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке: Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
Входные данные В первой строке входного файла находятся два натуральных числа N и M (1 ≤ N, M ≤ 15).
Выходные данные В выходной файл выведите единственное число количество способов добраться конём до правого нижнего угла доски.
Примеры входные данные 4 4 выходные данные 2 входные данные 7 15 выходные данные 13309
Пробовал решить так:
 read(n,m);
 a[1,1]:=1;
 a[0,3]:=1;
 a[3,0]:=1;
 For i:=1 to 15 do
  For j:=1 to 15 do
   a[i,j]:=a[i+1,j-2]+a[i-1,j-2]+a[i-2,j-1]+a[i-2,j+1];
 write(a[n,m]);
...но ничего не получилось, уже два часа бьюсь, не могу понять, что не так.


textual

Код к задаче: «Определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол - Free Pascal»

{$mode objfpc}
{$COPERATORS ON} //Чтобы можно было использовать +=
const MaxSize = 15;
var dp: array [1..MaxSize, 1..MaxSize] of int64;// Насколько я помню ответ там большой можем быть, потому лучше взять int64
    n, m: Integer;
    
function answer(i, j: Integer): int64;
begin
   if dp[i][j] >= 0 then Exit(dp[i][j]); 
   { Будем считать что если dp[i][j] = -1, то мы его еще не считали, а если мы уже считали это значение, тогда 
     возвращаем его и выходим из функции}
   dp[i][j] := 0;
   if i-2 >= 1 then begin // Проверяем границы чтоб не обратиться к элементу которого нет
      if j-1 >= 1 then dp[i][j] += answer(i-2, j-1); // прибавляем ответ
      if j+1 <= m then dp[i][j] += answer(i-2, j+1);
   end;
   if j-2 >= 1 then begin
      if i-1 >= 1 then dp[i][j] += answer(i-1, j-2);
      if i+1 <= n then dp[i][j] += answer(i+1, j-2);
   end;
   Result := dp[i][j];
end;
 
var i, j: Integer;
begin
   Readln(n, m);
   for i := 1 to n do
      for j := 1 to m do
         dp[i][j] := -1; // Изначально все пометим -1
   dp[1][1] := 1; // Кроме начального значения
   Write(answer(n, m));
end.
Эта работа вам не подошла?

Вы всегда можете заказать любую учебную работу у наших авторов от 20 руб.


СДЕЛАЙТЕ РЕПОСТ

11   голосов, оценка 3.818 из 5

Источник
Похожие ответы