洛谷算法

P1002 [NOIP 2002 普及组] 过河卒

题目描述

棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，$A$ 点 $(0, 0)$、$B$ 点 $(n, m)$，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 $B$ 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

样例 #1

样例输入 #1

6 6 3 3

样例输出 #1

6

提示

对于 $100 %$ 的数据，$1 \le n, m \le 20$，$0 \le$ 马的坐标 $\le 20$。

【题目来源】

NOIP 2002 普及组第四题

解题

#P1002
def calculate_path(n, m, horse_x, horse_y):
    # 马的八个可能移动方向
    moves = ((2,1), (2,-1), (-2,1), (-2,-1), (1,2), (1,-2), (-1,2), (-1,-2))
    
    # 创建控制点集合
    control_set = {(horse_x + dx, horse_y + dy) for dx, dy in moves 
                   if 0 <= horse_x + dx <= n and 0 <= horse_y + dy <= m}
    control_set.add((horse_x, horse_y))
    
    # 创建dp数组，初始化为0
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    # 设置起点
    dp[0][0] = 1 if (0, 0) not in control_set else 0
    
    # 动态规划计算路径数
    for i in range(n + 1):
        for j in range(m + 1):
            if (i, j) not in control_set:  # 如果当前点不在马的控制范围内
                if i > 0:  # 从上方来
                    dp[i][j] += dp[i-1][j]
                if j > 0:  # 从左方来
                    dp[i][j] += dp[i][j-1]
    
    return dp[n][m]

def check_input(n, m, horse_x, horse_y):
    """检查输入数据是否在有效范围内"""
    if not (1 <= n <= 20 and 1 <= m <= 20):
        return False, "棋盘大小超出范围！n和m应在1-20之间"
    if not (0 <= horse_x <= n and 0 <= horse_y <= m):
        return False, "马的位置超出棋盘范围！"
    return True, ""

# 提供输入提示
print("请输入棋盘大小(n,m)和马的位置(x,y)，用空格分隔")
print("数据范围：1 ≤ n,m ≤ 20；马的位置不能超出棋盘范围")
print("示例：6 6 3 3")

try:
    # 读取输入
    n, m, horse_x, horse_y = map(int, input().split())
    
    # 检查输入数据范围
    valid, error_msg = check_input(n, m, horse_x, horse_y)
    
    if not valid:
        print(error_msg)
    else:
        # 计算并输出结果
        result = calculate_path(n, m, horse_x, horse_y)
        print(f"从(0,0)到({n},{m})的路径数为：{result}")

except ValueError:
    print("输入格式错误！请输入4个整数，用空格分隔")
except Exception as e:
    print(f"发生错误：{str(e)}")