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()