Задача
Имеется клетчатое поле размером $m \times n$. В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. Перед тем как добраться до правого верхнего угла её заинтересовал вопрос: сколько существует способов добраться из исходной точки до правого верхнего угла?
Черепашка хотя и умная, но сама считать так много пока не умеет. Помогите черепашке найти ответ на свой вопрос.
Входные данные
Два натуральных числа $m$ и $n$, не превышающие $30$.
Выходные данные
Вывести количество способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний.
Тесты
| Входные данные | Выходные данные |
| $4$ $3$ | $10$ |
| $5$ $5$ | $70$ |
| $4$ $8$ | $120$ |
| $10$ $10$ | $48620$ |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int m = in.nextInt(); int n = in.nextInt(); long[][] a = new long[m][n]; a[m-1][0] = 1; for(int i = m-1; i >= 0; i--) { for(int j = 0; j < n; j++) { if(i == m-1 && j == 0) continue; a[i][j] = (i < m-1 ? a[i+1][j] : 0) + (j > 0 ? a[i][j-1] : 0); } } System.out.print(a[0][n-1]); } } |
Решение задачи
Для решения задачи представим, что черепашка уже находится в правом верхнем углу поля. Начинаем движение сверху-вниз справа-налево, т.е возможные ходы черепашки только наоборот(черепашка может ходит вверх и направо). Если черепашка сместилась вниз по карте, т.e. j > 0, то прибавляем ячейке значение верхней, если черепашка сместилась налево, т.e. i < m-1, то прибавляем ячейке значение правой. Эта сумма будет накапливаться и будет равна количеству всех возможных ходов черепашки. Проходя через всю карту, попадем в левую нижнюю ячейку(старт черепашки), эта ячейка и будет содержать число возможных путей к правой верхней точки. Задача решена.
Ссылки
Условие задачи на e-olymp
Код решения на ideone.com