题目大意:
棋盘上 A点有一个过河卒,需要走到目标 B 点。
卒行走的规则:向下或向右。
同时在棋盘上 C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。
棋盘用坐标表示,AA 点 (0,0)、BB 点 (n,m),同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A点能够到达 B 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。
对于 100% 的数据,1≤n,m≤201≤n,m≤20,0≤0≤ 马的坐标 ≤20≤20。
此题是初级二维DP
1.建立DP数组,dp[i][j]表示卒从A点到点(i,j)的方案数
2.由于卒只能向右或向下,所以当前位置是从dp[i-1][j]和dp[i][j-1]走来的,所以
dp[i][j]=dp[i-1][j]+dp[i][j-1]
3.注意题中下标是从0开始的,不方便,所以我们使下标整体+1
4.有马的存在,我们要跳过马和他的控制点
5. 4中的问题是马的控制点有可能越界,所以我们要把数组内移一位,像这样:
dp[i][j]->dp[i+2][j+2]
6.会爆int,要开long long
7.代码实现:
#include<bits/stdc++.h>
using namespace std;
long long dp[23][23];
int main(){
int xb,yb,xm,ym;
cin>>xb>>yb>>xm>>ym;
xb+=2;
yb+=2;
xm+=2;
ym+=2;
dp[2][2]=1;
for(int i=2;i<=xb;i++){
for(int j=2;j<=yb;j++){
if((i == xm+1 && j == ym+2)||
(i==xm+2 && j==ym+1)||
(i==xm+2 && j==ym-1)||
(i==xm+1 && j==ym-2)||
(i==xm-1 && j==ym-2)||
(i==xm-2 && j==ym-1)||
(i==xm-2 && j==ym+1)||
(i==xm-1 && j==ym+2)||
(i==xm && j==ym))
continue;
dp[i][j]+=dp[i-1][j]+dp[i][j-1];
}
}
cout<<dp[xb][yb];
return 0;
}
标签:洛谷,NOIP2002,int,题解,yb,long,ym,20,dp
From: https://blog.csdn.net/ghhvhgvugft/article/details/145286324