ПОМОГИТЕ С С++

Question

ПОМОГИТЕ С С++

leyla nuriyeva Ученик (86), открыт 3 недели назад

Дана прямоугольная доска n × m (n строк и m столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз. Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
Входные данные

4 4
Результат работы

2

Answer 1

 #include <iostream> 
#include <vector> 
 
using namespace std; 
 
int countKnightPaths(int n, int m) { 
    vector<vector<int>> dp(n, vector<int>(m, 0)); 
    dp[0][0] = 1; // Начальная позиция 
 
    for (int i = 0; i < n; ++i) { 
        for (int j = 0; j < m; ++j) { 
            // Проверяем возможность перехода с клетки (i-2, j-1) 
            if (i - 2 >= 0 && j - 1 >= 0) { 
                dp[i][j] += dp[i - 2][j - 1]; 
            } 
            // Проверяем возможность перехода с клетки (i-1, j-2) 
            if (i - 1 >= 0 && j - 2 >= 0) { 
                dp[i][j] += dp[i - 1][j - 2]; 
            } 
        } 
    } 
 
    return dp[n - 1][m - 1]; 
} 
 
int main() { 
    int n, m; 
    cout << "Введите размер доски (n и m): "; 
    cin >> n >> m; 
     
    int result = countKnightPaths(n, m); 
    cout << "Количество маршрутов: " << result << endl; 
     
    return 0; 
}

Answer 2

 #include <iostream> 
#include <vector> 
using namespace std; 
 
int main() { 
    int n, m; 
    cin >> n >> m; 
    vector<vector<long long>> dp(n, vector<long long>(m, 0)); 
    dp[0][0] = 1; 
 
    for (int i = 0; i < n; ++i) { 
        for (int j = 0; j < m; ++j) { 
            if (i - 2 >= 0 && j - 1 >= 0) 
                dp[i][j] += dp[i - 2][j - 1]; 
            if (i - 1 >= 0 && j - 2 >= 0) 
                dp[i][j] += dp[i - 1][j - 2]; 
        } 
    } 
    cout << dp[n - 1][m - 1] << endl; 
    return 0; 
}