Решение задачи #4 на Python с Яндекс CodeRun -Ход конём

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Название задачи: Ход конём.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:

Дана прямоугольная доска N×M (NN строк и MM столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. В данной задаче конь может перемещаться на две клетки вниз и одну клетку вправо или на одну клетку вниз и две клетки вправо.

Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.

Формат ввода:
Входной файл содержит два натуральных числа N и M (1⩽N, M⩽50).

Формат вывода:
В выходной файл выведите единственное число — количество способов добраться конём до правого нижнего угла доски.

Решение:

Python

def count_paths(n, m):
    """
    Считает количество путей коня по шахматной доске с ограниченными ходами.

    Args:
        n: Количество строк.
        m: Количество столбцов.

    Returns:
        Количество путей.
    """

    dp = [[0] * (m + 1) for _ in range(n + 1)]  # Матрица для динамического программирования
    dp[1][1] = 1  # Базовый случай

    for i in range(2, n + 1):
        for j in range(2, m + 1):
            dp[i][j] = dp[i - 2][j - 1] + dp[i - 1][j - 2]

    return dp[n][m]

# Считываем входные данные
n, m = map(int, input().split())

# Выводим результат
print(count_paths(n, m))

Объяснение кода

Инициализация матрицы dp:
Создаем матрицу dp размером (n+1) x (m+1), где каждый элемент будет хранить количество способов добраться до соответствующей клетки. Добавляем дополнительную строку и столбец, чтобы упростить индексацию при подсчете.

Базовый случай:
Устанавливаем dp[1][1] равным 1, так как существует только один способ добраться до начальной клетки.

Заполнение матрицы:
Проходим по всем клеткам матрицы, начиная с клетки (2, 2).
Для каждой клетки (i, j) считаем количество способов добраться до нее, сложив количество способов добраться до клеток (i-2, j-1) и (i-1, j-2). Эти две клетки являются единственными, из которых конь может попасть в клетку (i, j)согласно условиям задачи.

Возврат результата:
Возвращаем значение dp[n][m], которое хранит количество способов добраться до правого нижнего угла.

Источник решения: hdhAI.com