C语言程序设计 C语言程序设计

3.如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：只能向下或者向右。同
时，在棋盘上的任一点有一个对方的马（如图中点C),该马所在的点和所有跳跃一步可达的
点，称为马的控制点（如图中的9个控制点），卒不能通过对方马的控制点。请编程计算
从A点能够到达B点的路径的条数。
A
B
输入格式：只有一行，包含4个空格分隔的 输出格式：输出一个整数，为路径的条数 整数，即B点坐标(n,m)以及对方马的坐 标(x,y)
样例输出：
样例输入：
17
6632

【以下回答由 GPT 生成】

这个问题可以使用动态规划来解决。下面是解决该问题的具体步骤：

首先，将输入的四个整数解析出来，分别表示B点的坐标(n,m)以及敌方马的坐标(x,y)。

#include <stdio.h>

int main() {
    int n,m,x,y;
    scanf("%d %d %d %d", &n, &m, &x, &y);

    // 接下来的代码...
}

创建一个二维数组dp，用来保存到达每个点的路径条数，数组大小为(n+1) x (m+1)，并将所有元素初始化为0。

int dp[n+1][m+1];
memset(dp, 0, sizeof(dp));

将起始点A设为终点B的路径条数为1。

dp[n][m] = 1;

从终点B开始往起点A逐步计算路径条数。

for (int i = n; i >= 0; i--) {
    for (int j = m; j >= 0; j--) {
        // 如果当前点是敌方马的控制点，直接跳过
        if (i == x && j == y) {
            continue;
        }

        if (i < n) {
            dp[i][j] += dp[i+1][j];
        }
        if (j < m) {
            dp[i][j] += dp[i][j+1];
        }
    }
}

最后，输出起点A到终点B的路径条数。

printf("%d\n", dp[0][0]);

完整的C语言代码为：

#include <stdio.h>
#include <string.h>

int main() {
    int n,m,x,y;
    scanf("%d %d %d %d", &n, &m, &x, &y);

    int dp[n+1][m+1];
    memset(dp, 0, sizeof(dp));

    dp[n][m] = 1;

    for (int i = n; i >= 0; i--) {
        for (int j = m; j >= 0; j--) {
            if (i == x && j == y) {
                continue;
            }

            if (i < n) {
                dp[i][j] += dp[i+1][j];
            }
            if (j < m) {
                dp[i][j] += dp[i][j+1];
            }
        }
    }

    printf("%d\n", dp[0][0]);

    return 0;
}

这样，我们就可以计算出从点A能够到达点B的路径条数了。

【相关推荐】

这个问题的回答你可以参考下: https://ask.csdn.net/questions/7457443
我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：C语言程序设计程序设计与C语言
同时，你还可以查看手册：c语言-函数定义中的内容
您还可以看一下贺利坚老师的C语言及程序设计提高视频精讲课程中的模块化程序设计及C语言中的函数小节, 巩固相关知识点

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^


class Solution:
    def numPaths(self, n: int, m: int) -> int:
        dp = [[0] * (m+1) for _ in range(n+1)]
        dp[0][0] = 1
        for i in range(1, n+1):
            for j in range(1, m+1):
                if j == 0:
                    dp[i][j] = dp[i-1][j]
                elif j == i:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
        return dp[n][m]