c++【入门】跳马问题

Question

输入描述

只有一行：两个数n，m

输出描述

只有一个数：总方案数total

用例输入 1

4 8
用例输出 1

37

Answer 1

引自免费微信小程序：皆我百晓生

在解决这个问题时，我们可以使用动态规划的方法。设dp[i][j]表示从(0,0)到(i,j)的跳马路径数量。对于每一步，马可以向上或向下移动一格，同时向左或向右两格。因此，我们需要考虑当前坐标(i,j)的四个相邻位置(i-2,j+1), (i-2,j-1), (i+2,j+1), 和(i+2,j-1)，只要它们都在棋盘范围内并且没有被访问过。

以下是完整的C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m; // 输入棋盘大小n和m

    // 初始化一个二维动态规划数组
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    dp[0][0] = 1; // (0,0)只有一个起点

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (i > 0 && dp[i - 2][j + 1] > 0) { // 向上跳两格，向右跳一格
                dp[i][j] += dp[i - 2][j + 1];
            }
            if (i > 0 && j > 0 && dp[i - 2][j - 1] > 0) { // 向上跳两格，向左跳一格
                dp[i][j] += dp[i - 2][j - 1];
            }
            if (i < n && j < m && dp[i + 2][j + 1] > 0) { // 向下跳两格，向右跳一格
                dp[i][j] += dp[i + 2][j + 1];
            }
            if (i < n && j > 0 && dp[i + 2][j - 1] > 0) { // 向下跳两格，向左跳一格
                dp[i][j] += dp[i + 2][j - 1];
            }
        }
    }

    cout << dp[n][m] << endl; // 输出到达(m,n)的路径总数

    return 0;
}

这个程序首先初始化了一个二维动态规划数组dp，然后通过四重循环遍历整个棋盘，更新每个位置的路径数量。最终，dp[n][m]就是从(0,0)到(m,n)的所有合法路径的数量。

如果你有其他关于这段代码的问题或者需要进一步的解释，请随时告诉我。