Задача к ЕГЭ по информатике на тему «шахматные фигуры» №1

Ладья ходит по шахматной доске размера $10 × 10$ . Найдите модуль разности между количеством путей из точки $(1,1)$ в точку $(3,7)$ и количеством путей из точки $(1,1)$ в точку $(4,5)$ (первое число — номер строки, второе — номер столбца), если ладья может ходить только вверх и вправо.

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

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

$(1, 1),(1, 2),...,(1, 10),$

$(2, 1),(3, 1),...,(10, 1).$

Пусть $Aij$ — количество путей, ведущих в клетку $(i,j ).$

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

$A12 = A11,$

$A = A + A ,...,A = A + A + ...+ A . 13 11 12 110 11 12 19$

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

Динамически посчитаем все остальные $Aij$ способом, описанным выше, и ответом будет $|A37 − A45|$ .

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

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

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

Ответ: 271