На шахматной доске на клетке a1 стоит король, которому необходимо попасть на клетку h8, не попадая на клетки с3, с6, f3, f6. Король может двигаться только вверх или вправо на одну клетку. Сколькими способами это можно сделать?
Ответы
Ответ: 678 способами , король может добраться до клетки h8 , при этом не попадая на клетки с3, с6, f3, f6
Пошаговое объяснение:
Для решения данной воспользуемся динамическим программированием
Просто вручную последовательно заполняем табличку 7×7 (поскольку мы перемещаемся по узлам ) , складывая значения в граничащих с текущей узлах слева и снизу. То есть мы как бы складываем числа которые находятся по диагонали , а результат записываем в правом узле , число находящиеся в данном узле и будет кол-вом путей , которыми мы можем добраться из a1 до определенного узла , мы продолжаем данную операцию , до узла h8 , при этом этом не беря в счет пути которыми мы можем добраться из в a1 в c3,c6,f3,f6 т.е на данные точки мы ставим нолик
Заполнив таким образом табличку , мы получим 678 способов
#SPJ1
