С++ Каково количество возможных маршрутов игрока в прямоугольной таблице? В начале игрок находится в левом верхнем углу

Дарья_385

31

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

Изначально, dp[0][0] будет равно 1, так как игрок уже находится в начальной клетке. Затем, для каждой клетки (i, j) массива dp будем обновлять количество путей следующим образом: dp[i][j] = dp[i-1][j] + dp[i][j-1], что означает, что количество путей для достижения клетки (i, j) равно сумме количества путей до клетки выше (i-1, j) и количества путей до клетки слева (i, j-1).

После обновления всех элементов массива dp, количество возможных путей для игрока, чтобы достичь правой нижней клетки таблицы (N-1, M-1), будет содержаться в элементе dp[N-1][M-1].

Вот код на C++, реализующий это решение:

cpp

#include 

#include 



using namespace std;



int countPaths(int N, int M) {

    vector> dp(N, vector(M, 0));



    dp[0][0] = 1;



    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];

        }

    }



    return dp[N-1][M-1];

}



int main() {

    int N, M;

    cout << "Введите размеры таблицы (N и M): ";

    cin >> N >> M;



    int paths = countPaths(N, M);



    cout << "Количество возможных путей для игрока: " << paths << endl;



    return 0;

}

Этот код сначала запрашивает размеры таблицы с помощью ввода с клавиатуры. Затем вызывается функция countPaths, которая возвращает количество возможных путей, и результат выводится на экран.

Например, если ввести размеры 3 и 4, то программа выведет: "Количество возможных путей для игрока: 10". Это означает, что у игрока есть 10 различных маршрутов для достижения правой нижней клетки таблицы в этом примере.