Вопрос Задача "Шашки", питон

[ilyuxa]

Помогите пожалуйста решит задачу:
На шахматной доске (8x8) стоит одна белая шашка. Сколькими способами она может пройти в дамки?

(Белая шашка ходит по диагонали. на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)

Входные данные
Вводятся два числа от 1 до 8: номер номер столбца (считая слева) и строки (считая снизу), где изначально стоит шашка.

Выходные данные
Вывести одно число - количество путей в дамки.

Примеры
входные данные
3 7
выходные данные
2
входные данные
1 8
выходные данные
1
входные данные
3 6
выходные данные
4

 

[beshen]

Ну, считай. Примерно так (для черной): __X__ (шашка) _1_1_ (2 клетки по одному способу) 1_2_1 (3 клетки по 2 способа) и т. д. 2 в центре - сумма единичек сверху по диагоналям от нее. Тебе нужна сумма последней строки.

 

[Даниял_]

Вам нужно написать код или вы не знаете какой алгоритм применить? Если второе, то мне кажется, это можно решить динамическим программированием. Динамикой будет число путей в конкретную клетку. Если мы рассчитаем кол-во путей для всех клеток, то ответом будет сумма путей для клеток верхней горизонтали. Будем считать, что нижняя горизонталь - 1я строка матрицы 8х8. Все элементы матрицы равны 0. Когда мы получили координаты шашки, присваиваем соответствующему элементу матрицы 1. Затем обходим матрицу построчно начиная с 2ой строки. Каждой клетке присваиваем сумму нижних диагональных клеток (откуда мы можем дойти к текущей клетке). В конце работы алгоритма в 8ой строке будут клетки с количеством путей, которыми можно до них дойти. Нам нужно их просуммировать и это будет ответом.