笔试训练48天：过河卒

[NOIP2002 普及组] 过河卒_牛客题霸_牛客网https://www.nowcoder.com/practice/cc1a9bc523a24716a117b438a1dc5706?tpId=230&tqId=40428&ru=/exam/oj知识点动态规划

描述

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

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

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

注：马一次跳跃到达的点(x1,y1)和马原坐标(x,y)的关系是 ∣x1−x∣+∣y1−y∣=3，且x1≠x,y1≠y

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

1≤a,b,c,d≤1000 1≤a,b,c,d≤1000

输入描述：

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

输出描述：

输出路径总数

示例1

输入：6 6 3 3 输出：6

示例2

输入：5 4 2 3 输出：3

示例3

输入：2 5 3 5 输出：1

思路：动态优化

1.dp[i][j]状态表示:从[0][0]位置出发，到达[i][j]位置一共有多少种方法

2.状态转移方程:①dp[i][j]=dp[i][j-1]+dp[i-1][j]

②若果走不到里面为0

3.初始化

多加一行一列,dp[0][1]=1或者dp[1][0]=1;初始位置本来就是一个占位

#include <cwctype> #include <iostream> using namespace std; int n,m,x,y; long long dp[25][25]; int main() { cin>>n>>m>>x>>y; x+=1;y+=1; dp[0][1]=1; for(int i=1;i<=n+1;i++) { for(int j=1;j<=m+1;j++) { if(i!=x&&j!=y && abs(i-x)+abs(j-y)==3||(i==x&&j==y)) { dp[i][j]=0; } else { dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } } cout<<dp[n+1][m+1]<<endl; return 0; }