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