Question

Шашку — в дамки ДАЮ 100 БАЛЛОВ!!!! НА ПИТОНЕ С ИСПОЛЬЗОВАНИЕМ ДВУМЕРНОГО МАССИВА На шахматной доске (8×8) стоит одна белая шашка. Сколькими способами она может пройти в дамки? (Белая шашка ходит по диагонали. на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.) Входные данные Вводятся два числа от 1 до 8: номер номер столбца (считая слева) и строки (считая снизу), где изначально стоит шашка. Выходные данные Вывести одно число — количество путей в дамки. Примеры Ввод 3 7 1 8 3 6 Вывод 2 1 4 СРОЧНО

Answer 1

Алгоритм: положим в ячейку, где стоит шашка, значение 1. В некоторую ячейку с горизонталью i и вертикалью j можно добраться из клеток (i-1, j-1) и (i-1, j+1), если эти клетки существуют. Тогда для двумерного массива A, выступающего в роли доски, будет справедливо следующее утверждение: A[i+1][j] = A[i][j-1] + A[i][j+1]. Существовать ячейки не будут, если находятся в крайних столбцах: A[i+1][0] = A[i][1] и A[i+1][7] = A[i][6].

Программа:

y, x = map(int, input().split())

x, y = x - 1, y - 1

board = [[0]*8 for i in range(8)]

board[x][y] = 1

for i in range(x, 7):

   board[i+1][0] += board[i][1]

   for j in range(1, 7):

       board[i+1][j] += board[i][j-1] + board[i][j+1]

   board[i+1][7] += board[i][6]

print(sum(board[7]))

Answer 2

Для решения этой задачи можно воспользоваться динамическим программированием. Создадим двумерный массив размером 8x8, где значение в ячейке (i, j) будет представлять количество способов достичь клетки (i, j) из начальной позиции.

Изначально, начиная с позиции шашки, установим значение 1. Затем будем заполнять массив, двигаясь по диагонали вверх-вправо и вверх-влево, добавляя к текущей ячейке значение из предыдущей ячейки по диагонали влево и вправо. Таким образом, в каждой ячейке будет сумма способов достижения предыдущих двух ячеек.

Вот код на Python, который решает эту задачу:

pythonCopy code
def count_ways_to_promotion(start_row, start_col):
    # Создаем массив для хранения количества способов достижения каждой клетки
    dp = [[0] * 8 for _ in range(8)]

    # Начальная позиция
    dp[start_row][start_col] = 1

    # Двигаемся по доске и обновляем значения в массиве dp
    for row in range(start_row, 8):
        for col in range(8):
            if dp[row][col] > 0:
                # Движение по диагонали вверх-вправо
                if col < 7:
                    dp[row + 1][col + 1] += dp[row][col]
                # Движение по диагонали вверх-влево
                if col > 0:
                    dp[row + 1][col - 1] += dp[row][col]

    # Возвращаем количество способов достижения верхней горизонтали
    return sum(dp[7])

# Чтение входных данных
start_col, start_row = map(int, input().split())

# Вызов функции и вывод результата
print(count_ways_to_promotion(8 - start_row, start_col - 1))

Вызов функции count_ways_to_promotion с соответствующими координатами начальной позиции (преобразованными в индексы массива) вернет количество способов достичь верхней горизонтали доски.

Пример использования:

makefileCopy code
Ввод:
3 7
Вывод:
2

makefileCopy code
Ввод:
1 8
Вывод:
1

makefileCopy code
Ввод:
3 6
Вывод:
4