Определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол - 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.
Объяснение кода листинга программы
- Входные данные: n, m (размеры сетки)
- Создание массива dp для хранения промежуточных результатов
- Инициализация всех элементов dp[-1, -1] = -1 (помечаем как не просчитанные)
- Инициализация начального элемента dp[1][1] = 1
- Функция answer: рекурсивный подсчет количества путей от левого верхнего до правого нижнего угла
- Проверка базового случая: если dp[i][j] уже есть, то возвращаем его и выходим из функции
- Рекурсивный вызов функции answer для четырех соседей элемента i, j (вверх, вниз, влево, вправо)
- Суммируем результаты рекурсивных вызовов
- Возвращаем итоговое значение dp[i][j]
- Заполнение массива dp значениями от 1 до n*m (помечаем как просчитанные)
- Вывод результата в консоль
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д