М
Молодежь
К
Компьютеры-и-электроника
Д
Дом-и-сад
С
Стиль-и-уход-за-собой
П
Праздники-и-традиции
Т
Транспорт
П
Путешествия
С
Семейная-жизнь
Ф
Философия-и-религия
Б
Без категории
М
Мир-работы
Х
Хобби-и-рукоделие
И
Искусство-и-развлечения
В
Взаимоотношения
З
Здоровье
К
Кулинария-и-гостеприимство
Ф
Финансы-и-бизнес
П
Питомцы-и-животные
О
Образование
О
Образование-и-коммуникации
sd16sv
sd16sv
22.03.2020 05:32 •  Информатика

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

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

Входные данные

В первой строке входного файла находятся два натуральных числа N и M (1≤N,M≤15).

Выходные данные

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

Примеры
Ввод
4 4
Вывод
2
Ввод
7 15
Вывод На любом из языков(Java)(C++)(Python)

👇
Ответ:
73021081
73021081
22.03.2020
Для решения данной задачи можно использовать динамическое программирование.

Введем двумерный массив 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), что является эффективным для указанных ограничений размера доски.
4,6(39 оценок)
Проверить ответ в нейросети
Новые ответы от MOGZ: Информатика
logo
Вход Регистрация
Что ты хочешь узнать?
Спроси Mozg
Открыть лучший ответ