K. 【提高】过河卒 传统题 1000ms 16MiB 说明 A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如下图的C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如下图 C 点可以控制 9 个点(图中的P1,P2 … P8 和 C)。卒不能通过对方马的控制点。 棋盘用坐标表示,现给定A 点位置为(0,0)B 点位置为(n,m)(n,m 为不超过 20 的整数),马的位置为C(X,Y)(约定: C点与A点不重叠,与B点也不重叠)。要求你计算出卒从 A 点能够到达 B 点的路径的条数。

输入格式 B点的坐标(n,m)以及对方马的坐标(X,Y)(马的坐标一定在棋盘范围内,但要注意,可能落在边界的轴上)

样例 输入数据 1 6 6 3 2 输出数据 1 17

3 条评论

  • @ 2026-4-8 16:43:10

    hi

    ❤️ 2
    • @ 2026-4-6 7:48:22

      谢谢

      👍 2
      ❤️ 2
      😄 2
      • @ 2026-4-5 23:10:32

        @

        定义 dp[1...n][1...m] 数组表示到第 (i,j) 有多少路径。从 (0,0) 开始(dp[0][0]等于 1,即有一条路),每格的路径数就是上方的路径数(从上方来)加上左方的路径数(从左方来)。最后输出 dp[n][m]。状态转移方程:

        $$\begin{aligned} dp[i][j] &= \begin{cases} 1 & i=j=1 \\ dp[i-1][j] + dp[i][j-1] & i>1,j>1 \end{cases} \end{aligned}$$
        ❤️ 2
        👍 2
        😄 2
        🍋 2
        • 1