Женя очень любит решать шахматные задачки, особенно про коней. Но на этот раз вместо коня ему подсунули верблюда. Верблюд - особенная шахмат...
Условие:
Женя очень любит решать шахматные задачки, особенно про коней. Но на этот раз вместо коня ему подсунули верблюда. Верблюд - особенная шахматная фигура, которая может за один ход сместиться на одну клетку вправо или на одну клетку вверх, причём первая координата клетки всегда должна быть больше, чем вторая, или равна ей ( X ≥ Y ) (X≥Y).
У Жени ест
Решение:
У Жени есть шахматная доска размером N x M клеток, где N - количество строк, а M - количество столбцов. Он хочет узнать, сколько возможных ходов может сделать верблюд с определенной стартовой позиции на доске.
Для решения этой задачи можно использовать динамическое программирование. Создадим двумерный массив dp размером N x M, где dp[i][j] будет хранить количество возможных ходов верблюда, чтобы добраться до клетки (i, j).
Инициализируем dp[0][0] = 1, так как верблюд уже находится в стартовой позиции.
Затем, для каждой клетки (i, j), начиная с (0, 0) и двигаясь по строкам и столбцам, будем вычислять количество возможных ходов верблюда, используя значения предыдущих...
