我要招人

去企业版

首页 > 试题广场 >

[NOIP2002 普及组] 过河卒

[编程题][NOIP2002 普及组] 过河卒

热度指数：4429 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

注：马一次跳跃到达的点(x1,y1)和马原坐标(x,y)的关系是 $|x1-x|+|y1-y|=3 ，且x1 \neq x ,y1\neq y \$

数据范围： $1 \le n,m \le 20\$ ，马的坐标 $0 \le x,y \le 20 \$

$1 \le a,b,c,d \le 1000 \$

输入描述:

仅一行，输入 n,m,x,y 四个正整数。分别表示B点坐标和马的坐标

输出描述:

输出路径总数

示例1

输入

6 6 3 3

输出

示例2

输入

5 4 2 3

输出

示例3

输入

2 5 3 5

输出

算法知识视频讲解

静寂旮旯

发表于 2022-04-13 14:03:33

解题思路：利用二维数组dp 卒子只能两个方向走，一个是向右，一个是向下。可得状态方程dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1]。在处理马点的时候，应展开全文

充电中...

发表于 2022-06-30 15:37:53

都没有人用C写，那我写一个 #include <stdio.h> int fun(int x,int y,int n,int m); int main(){ int n = 0,m = 0,x = 0,y = 0; sc 展开全文

吱吱1111111

发表于 2024-04-17 04:31:31

#include <iostream> #include <vector> using namespace std; struct point{ int x; int y; point(int a=0,int b=0):x(a),y(b){} }; 展开全文

-含章可贞-

发表于 2022-05-16 11:41:05

n,m,x,y=map(int,input().split()) assert(1<=n<=20) assert(1<=m<=20) assert(0<=x<=20) assert(0<=y<=20) board=[[1 for _ in range( 展开全文

sum～

发表于 2022-03-21 11:10:38

(1)dp数组含义：dp[x][y]表示到达(x, y)的路径条数 (2)递推公式：dp[i][j] = dp[i-1][j] + dp[i][j - 1];(因为卒只可以向右或者向下走) (3)初始化：dp[0][0] = 1,根据马的坐标(x, y)，可以将(x,y)和马可以到达的八个点的坐标对展开全文

编程小鹏

发表于 2024-04-09 21:28:16

import java.util.Arrays; import java.util.Scanner; public class Main { static int N = 21; public static void main(String[] args) { Scanner in = n 展开全文