Ход конем
Дана прямоугольная доска N∗M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:
Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
Входные данные
В первой строке входного файла находятся два натуральных числа N и M (1≤N,M≤15).
Выходные данные
В выходной файл выведите единственное число — количество добраться конём до правого нижнего угла доски.
Примеры
Ввод
4 4
Вывод
2
Ввод
7 15
Вывод На любом из языков(Java)(C++)(Python)
Введем двумерный массив dp размером (N+1)×(M+1), в котором dp[i][j] будет хранить количество различных маршрутов, ведущих из левого верхнего угла доски в клетку (i,j).
Инициализируем массив dp следующим образом:
- dp[0][0] = 1 (начальная клетка)
- dp[1][2] = 1 (второй ход коня)
- dp[2][1] = 1 (второй ход коня)
Затем переберем все клетки доски по строкам и столбцам, начиная с (1,1), и заполним массив dp по формуле:
- dp[i][j] = dp[i-1][j-2] + dp[i-2][j-1]
То есть количество путей до клетки (i,j) равно сумме количества путей до клеток, из которых конь может сделать ход в клетку (i,j).
Наконец, ответом на задачу будет являться значение dp[N][M].
Пример решения на языке Python:
```python
N, M = map(int, input().split())
dp = [[0] * (M+1) for _ in range(N+1)]
dp[0][0] = 1
dp[1][2] = 1
dp[2][1] = 1
for i in range(1, N+1):
for j in range(1, M+1):
dp[i][j] = dp[i-1][j-2] + dp[i-2][j-1]
print(dp[N][M])
```
Данное решение имеет сложность O(N*M), что является эффективным для указанных ограничений размера доски.