e-olymp 1704. Умная черепашка

Задача

Карта, где ходит черепашка
Имеется клетчатое поле размером $m \times n$. В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. Перед тем как добраться до правого верхнего угла её заинтересовал вопрос: сколько существует способов добраться из исходной точки до правого верхнего угла?

Черепашка хотя и умная, но сама считать так много пока не умеет. Помогите черепашке найти ответ на свой вопрос.

Входные данные

Два натуральных числа $m$ и $n$, не превышающие $30$.

Выходные данные

Вывести количество способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний.

Тесты

Входные данные Выходные данные
$4$ $3$ $10$
$5$ $5$ $70$
$4$ $8$ $120$
$10$ $10$ $48620$

Код программы

Решение задачи

Для решения задачи представим, что черепашка уже находится в правом верхнем углу поля. Начинаем движение сверху-вниз справа-налево, т.е возможные ходы черепашки только наоборот(черепашка может ходит вверх и направо). Если черепашка сместилась вниз по карте, т.e. j > 0, то прибавляем ячейке значение верхней, если черепашка сместилась налево, т.e. i < m-1, то прибавляем ячейке значение правой. Эта сумма будет накапливаться и будет равна количеству всех возможных ходов черепашки. Проходя через всю карту, попадем в левую нижнюю ячейку(старт черепашки), эта ячейка и будет содержать число возможных путей к правой верхней точки. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *