Дана прямоугольная доска n×m (n строк и m столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:

Здравствуйте! Это классическая задача на поиск количества путей на сетке с ограниченными ходами, которую удобно решать с помощью динамического программирования (ДП).

Поскольку размеры доски $N$ и $M$ очень малы ($N, M \le 15$), ДП является оптимальным подходом.

1. Дано

• Размеры доски: $N$ строк и $M$ столбцов.
• Начальная позиция: Левый верхний угол (координаты $(1, 1)$).
• Конечная позиция: Правый нижний угол (координаты $(N, M)$).
• Допустимые ходы коня: Ходы "буквой Г" (сдвиг на 2 по одной оси и 1 по другой).

2. Найти

Количество различных способов добраться из $(1, 1)$...