P1002 过河卒

May 4, 2026 · 7 分钟阅读 · 动态规划 ·

文章目录

题目信息

字段	内容
题号	P1002
难度	橙题（普及-）
知识点	动态规划、棋盘型DP

题目描述

有一个 n × m 的棋盘（中国象棋棋盘），卒从左上角 (0, 0) 出发，要到达右下角 (n, m)。棋盘上有一匹马，位置在 (x, y)。象棋马的走法是「日」字，马所在的格子以及马下一步能跳到的 8 个位置都会被控制，卒不能经过这些格子。

求从 (0, 0) 到 (n, m) 共有多少条不同的路径（只能向右或向下走）。

输入格式：四个整数 n, m, x, y，空格分隔。

输出格式：一个整数，表示路径数量。

解题思路

核心思想

分两步走：

标记禁区：马在 (x, y) 位置，会控制周围的 8 个格子。先把这些格子标记为不可达。
方向 DP：棋盘上只能向右或向下走，所以每个格子的路径数 = 从上方来的 + 从左方来的，这就是经典的棋盘路径 DP。

马的控制范围

与中国象棋的马走法一致，从 (x, y) 出发共 8 个目标位置：

(x-2)
- (y-1)
- (y+1)
(x+2)
- (y-1)
- (y+1)
(x-1)
- (y-2)
- (y+2)
(x+1)
- (y-2)
- (y+2)

超出棋盘边界的格子直接忽略。

为什么用动态规划？

因为只能向右或向下走，棋盘形成了一个 DAG（有向无环图）。从左到右、从上到下按顺序遍历，每个格子只会被访问一次，时间复杂度是 O(n×m)。

完整代码

C++

#include <iostream>

using namespace std;

// 马的八个跳跃方向（象棋马走日字）
const int kDx[9] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
const int kDy[9] = {0, 2, 1, -1, -2, -2, -1, 1, 2};

long long dp[30][30];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, m, x, y;
    cin >> n >> m >> x >> y;

    // dp 数组大小为 (n+1) × (m+1)，索引范围 0~n 和 0~m
    // 标记禁区：马所在格及其控制格
    for (int i = 0; i <= 8; i++) {
        int tx = x + kDx[i];
        int ty = y + kDy[i];
        if (tx >= 0 && tx <= n && ty >= 0 && ty <= m) {
            dp[tx][ty] = -1;  // -1 表示不可达
        }
    }

    // 方向 DP：只能从上方或左方到达
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (dp[i][j] != -1) {
                long long from_top = 0;
                long long from_left = 0;
                if (i - 1 >= 0 && dp[i - 1][j] != -1) {
                    from_top = dp[i - 1][j];
                }
                if (j - 1 >= 0 && dp[i][j - 1] != -1) {
                    from_left = dp[i][j - 1];
                }
                dp[i][j] = from_top + from_left;
                if (i == 0 && j == 0) {
                    dp[i][j] = 1;  // 起点有一种方式
                }
            }
        }
    }

    cout << dp[n][m] << "\n";
    return 0;
}

关键代码讲解

1. 禁区标记

const int kDx[9] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
const int kDy[9] = {0, 2, 1, -1, -2, -2, -1, 1, 2};

dx[0] 和 dy[0] 都是 0，表示马所在的自身格子也要标记为禁区。其余 8 个是标准象棋马的跳跃偏移量。

if (tx >= 0 && tx <= n && ty >= 0 && ty <= m) {
    dp[tx][ty] = -1;  // 在棋盘范围内才标记
}

边界检查必不可少，否则数组会越界。

2. 方向 DP 转移

dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);

由于棋盘只能从左和从上两个方向到达，状态转移方程就是上方的路径数加上左方的路径数。

3. 起点的特殊处理

if (i == 0 && j == 0) dp[i][j] = 1;

左上角 (0, 0) 没有上方也没有左方，特殊处理为 1（自己算一种走法）。

复杂度分析

方法	时间复杂度	空间复杂度
棋盘 DP	O(n × m)	O(n × m)

n, m ≤ 25，复杂度完全足够。

易错点

索引范围：棋盘大小是 (n+1) × (m+1)，循环上界要用 <= n 和 <= m
马的控制范围包括自身：dx[0]=0, dy[0]=0 不要漏掉，否则起点或终点恰好是马的位置时会算错
负数索引：边界检查 <= n 和 <= m 不能写成 < n 和 < m
long long：路径数可能很大，答案会超过 int 范围，必须用 long long

其他语言解法

Python

"""P1002 过河卒 - Python 实现"""
from typing import List


def solve() -> None:
    """读取输入，计算从 (0,0) 到 (n,m) 的路径数"""
    n, m, x, y = map(int, input().split())

    # dp[i][j]: 到达 (i, j) 的路径数，-1 表示不可达
    dp: List[List[int]] = [[0] * (m + 1) for _ in range(n + 1)]

    # 马的八个跳跃方向
    k_dx = [0, 1, 2, 2, 1, -1, -2, -2, -1]
    k_dy = [0, 2, 1, -1, -2, -2, -1, 1, 2]

    # 标记禁区
    for i in range(9):
        tx = x + k_dx[i]
        ty = y + k_dy[i]
        if 0 <= tx <= n and 0 <= ty <= m:
            dp[tx][ty] = -1

    # 方向 DP
    for i in range(n + 1):
        for j in range(m + 1):
            if dp[i][j] != -1:
                if i == 0 and j == 0:
                    dp[i][j] = 1
                else:
                    from_top = dp[i - 1][j] if i > 0 and dp[i - 1][j] != -1 else 0
                    from_left = dp[i][j - 1] if j > 0 and dp[i][j - 1] != -1 else 0
                    dp[i][j] = from_top + from_left

    print(dp[n][m])


if __name__ == "__main__":
    solve()

Java

import java.io.IOException;

public class Main {
    // 洛谷强制要求类名为 Main，禁止使用 Scanner，用 BufferedInputStream
    private static final byte[] buffer = new byte[1 << 16];
    private static int ptr = 0;
    private static int len = 0;

    private static int read() throws IOException {
        if (ptr >= len) {
            len = System.in.read(buffer);
            ptr = 0;
            if (len <= 0) return -1;
        }
        return buffer[ptr++];
    }

    private static final int[] kDx = {0, 1, 2, 2, 1, -1, -2, -2, -1};
    private static final int[] kDy = {0, 2, 1, -1, -2, -2, -1, 1, 2};

    public static void main(String[] args) throws IOException {
        long n = readInt();
        long m = readInt();
        long x = readInt();
        long y = readInt();

        long[][] dp = new long[(int) (n + 1)][(int) (m + 1)];

        // 标记禁区
        for (int i = 0; i <= 8; i++) {
            int tx = (int) (x + kDx[i]);
            int ty = (int) (y + kDy[i]);
            if (tx >= 0 && tx <= n && ty >= 0 && ty <= m) {
                dp[tx][ty] = -1;
            }
        }

        // 方向 DP
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (dp[i][j] != -1) {
                    if (i == 0 && j == 0) {
                        dp[i][j] = 1;
                    } else {
                        long fromTop = (i > 0 && dp[i - 1][j] != -1) ? dp[i - 1][j] : 0;
                        long fromLeft = (j > 0 && dp[i][j - 1] != -1) ? dp[i][j - 1] : 0;
                        dp[i][j] = fromTop + fromLeft;
                    }
                }
            }
        }

        System.out.println(dp[(int) n][(int) m]);
    }

    private static long readInt() throws IOException {
        int c;
        do {
            c = read();
        } while (c <= ' ' && c != -1);
        boolean negative = false;
        if (c == '-') {
            negative = true;
            c = read();
        }
        long val = 0;
        while (c > ' ') {
            val = val * 10 + (c - '0');
            c = read();
        }
        return negative ? -val : val;
    }
}

Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

var (
    kDx = [9]int{0, 1, 2, 2, 1, -1, -2, -2, -1}
    kDy = [9]int{0, 2, 1, -1, -2, -2, -1, 1, 2}
)

func main() {
    in := bufio.NewReader(os.Stdin)

    var n, m, x, y int
    fmt.Fscan(in, &n, &m, &x, &y)

    dp := make([][]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, m+1)
    }

    // 标记禁区
    for i := 0; i <= 8; i++ {
        tx := x + kDx[i]
        ty := y + kDy[i]
        if tx >= 0 && tx <= n && ty >= 0 && ty <= m {
            dp[tx][ty] = -1
        }
    }

    // 方向 DP
    for i := 0; i <= n; i++ {
        for j := 0; j <= m; j++ {
            if dp[i][j] != -1 {
                if i == 0 && j == 0 {
                    dp[i][j] = 1
                } else {
                    fromTop := 0
                    fromLeft := 0
                    if i > 0 && dp[i-1][j] != -1 {
                        fromTop = dp[i-1][j]
                    }
                    if j > 0 && dp[i][j-1] != -1 {
                        fromLeft = dp[i][j-1]
                    }
                    dp[i][j] = fromTop + fromLeft
                }
            }
        }
    }

    fmt.Println(dp[n][m])
}

JavaScript

'use strict';

/**
 * 马的八个跳跃方向（象棋马走日字）
 * @type {number[]}
 */
const kDx = [0, 1, 2, 2, 1, -1, -2, -2, -1];
const kDy = [0, 2, 1, -1, -2, -2, -1, 1, 2];

/**
 * 主函数：从 (0,0) 到 (n,m) 的路径数，排除马的控制点
 */
function main() {
    const input = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split(/\s+/);
    const [n, m, x, y] = input.map(Number);

    /** @type {number[][]} */
    const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));

    // 标记禁区：马所在格及其控制格
    for (let i = 0; i <= 8; i++) {
        const tx = x + kDx[i];
        const ty = y + kDy[i];
        if (tx >= 0 && tx <= n && ty >= 0 && ty <= m) {
            dp[tx][ty] = -1;
        }
    }

    // 方向 DP：只能从上方或左方到达
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= m; j++) {
            if (dp[i][j] !== -1) {
                if (i === 0 && j === 0) {
                    dp[i][j] = 1;
                } else {
                    const fromTop = (i > 0 && dp[i - 1][j] !== -1) ? dp[i - 1][j] : 0;
                    const fromLeft = (j > 0 && dp[i][j - 1] !== -1) ? dp[i][j - 1] : 0;
                    dp[i][j] = fromTop + fromLeft;
                }
            }
        }
    }

    console.log(dp[n][m]);
}

main();