Question

С++ Количество маршрутов в прямоугольной таблице В прямоугольной таблице N×M вначале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку. Входные данные Вводятся два числа N и M — размеры таблицы 1≤N≤10,1≤M≤10. Выходные данные Выведите искомое количество способов. Примеры Ввод Вывод 1 10 1

Answer 1

Ответ:

#include <iostream>

using namespace std;

int x, y, value = 0;

void calc(int px, int py){

   if(px == x - 1 && py == y - 1) {

       value++;

       return;

   }

   if(px + 1 < x) calc(px + 1, py);

   if(py + 1 < y) calc(px, py + 1);

}

int main(){

   cin >> x >> y;

   calc(0, 0);

   cout << value;

   return 0;

}

Объяснение:

Сделал "по-тупому": рекурсией.

P. s. Если Вам помог ответ, отметьте его как лучший и жмякните на "Спасибо", пожалуйста. Это мотивирует продолжать давать ответы дальше.

Answer 2

Для решения этой задачи можно воспользоваться динамическим программированием. Создадим двумерный массив dp[N][M], где dp[i][j] будет представлять количество способов добраться из клетки (0, 0) в клетку (i, j).

Изначально, у нас есть только один способ добраться до клетки (0, 0) - это остаться в ней, поэтому dp[0][0] = 1.

Затем мы можем заполнить массив dp следующим образом:

1. dp[i][j] = dp[i-1][j] (если i > 0) - это означает, что мы двигаемся вниз из клетки выше.
2. dp[i][j] = dp[i][j-1] (если j > 0) - это означает, что мы двигаемся вправо из клетки слева.

Итак, начнем с клетки (0, 0) и последовательно заполняем массив dp до клетки (N-1, M-1).

Вот C++ код для решения этой задачи:

cppCopy code
#include <iostream>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    
    // Создаем массив dp и инициализируем его нулями
    int dp[11][11] = {0};
    
    // Исходная клетка (0, 0) имеет один способ достижения
    dp[0][0] = 1;
    
    // Заполняем массив dp
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (i > 0)
                dp[i][j] += dp[i-1][j];
            if (j > 0)
                dp[i][j] += dp[i][j-1];
        }
    }
    
    // Выводим количество способов достижения клетки (N-1, M-1)
    cout << dp[N-1][M-1] << endl;
    
    return 0;
}

Пример ввода:

Copy code
1 10

Пример вывода:

Copy code
1

Этот код решает задачу для таблицы размером 1x10, но он легко адаптируется для таблиц другого размера.