Определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол - 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
Листинг программы
{$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.

Объяснение кода листинга программы

  1. Входные данные: n, m (размеры сетки)
  2. Создание массива dp для хранения промежуточных результатов
  3. Инициализация всех элементов dp[-1, -1] = -1 (помечаем как не просчитанные)
  4. Инициализация начального элемента dp[1][1] = 1
  5. Функция answer: рекурсивный подсчет количества путей от левого верхнего до правого нижнего угла
  6. Проверка базового случая: если dp[i][j] уже есть, то возвращаем его и выходим из функции
  7. Рекурсивный вызов функции answer для четырех соседей элемента i, j (вверх, вниз, влево, вправо)
  8. Суммируем результаты рекурсивных вызовов
  9. Возвращаем итоговое значение dp[i][j]
  10. Заполнение массива dp значениями от 1 до n*m (помечаем как просчитанные)
  11. Вывод результата в консоль

Оцени полезность:

11   голосов , оценка 3.818 из 5
Похожие ответы