18.06 Шахматные фигуры

Решение руками

Сначала посчитаем, количество путей в ячейки

Пусть — количество путей, ведущих в клетку

(т.к. мы стартуем из этой клетки),

Аналогично с Далее заметим, что количество способов попасть в любую клетку, это сумма всех клеток, которые находятся ниже и левее данной.

Динамически посчитаем все остальные способом, описанным выше, и ответом будет .

Пример программы на для решения данной задачи. В программе все индексы на меньше, т.к. нумерация начинается с .

Решение программой

dp = []
for i in range(10):
    a = []
    for j in range(10):
        a.append(0)
    dp.append(a)
# dp[i][j] - количество способов прийти в клетку с номерами i и j
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# т.к. в питоне индексация с нуля, то dp[0][0] будет обозначать клетку
# с номером строки 1 и с номером столбца 1
dp[9][0] = 1  # сколько существует способов попасть из клетки (1, 1) в неё же?
# Ответ: ровно 1 способ - ничего не делать
for i in range(9, -1, -1):
    for j in range(10):
        for k in range(1, 10):
            if i == 9:
                if j - k >= 0:
                    dp[i][j] += dp[i][j - k]
            elif j == 0:
                if i + k < 10:
                    dp[i][j] += dp[i + k][j]
            else:
                if i + k < 10:
                    dp[i][j] += dp[i + k][j]
                if j - k >= 0:
                    dp[i][j] += dp[i][j - k]
# ответ
print(abs(dp[7][6] - dp[6][4]))
# выведем табличку для наглядности
print(" " * 7, end="")
for k in range(1, 11):
    print(f"{k:>10}", end="")
print()
print("-" * 112)
for i in range(10):
                                                                                                    
                                                                                                    
    for j in range(10):
        if j == 0:
            print(f"{10 - i:>10}|", end="")
        print(f"{dp[i][j]:>10}", end="")
    print()