2470: 【普及-】【P1002】过河卒
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：32
解决：7
题目描述
棋盘上 点有一个过河卒，需要走到目标 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示， 点 、 点 ，同样马的位置坐标是需要给出的。
现在要求你计算出卒从 点能够到达 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入
一行四个正整数，分别表示 点坐标和马的坐标。
输出
一个整数，表示所有的路径条数。
样例输入 复制
6 6 3 3样例输出 复制
6提示
对于 的数据，， 马的坐标 。
#include <iostream>
#define MAXN 22
using namespace std;
long long f[MAXN][MAXN]={0};
int ctrl [MAXN][MAXN],n,m,hx,hy;
int d[9][2]={{0,0},{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
// 马的控制范围相对于马位置的偏移量
int main() {
cin>>n>>m>>hx>>hy;
for(int i=0;i<9;i++){
int tmpx=hx+d[i][0],tmpy=hy+d[i][1];
if (tmpx>=0&&tmpx<=n&&tmpy>=0&&tmpy<=m)
//判断在棋盘范围内
ctrl[tmpx][tmpy]=1;
//记录马的控制点
}
f[0][0]=1-ctrl[0][0];
//若原点就是马控制点，那初始数量是0，否则1
for(int i=1;i<=n;i++) { //第1列都是f[0][0]；
if (ctrl[i][0]) break; //马控制点及其行后面的点都是0；
f[i][0]=f[0][0];
}
for(int j=1;j<=m;j++) { //第1行都是f[0][0]；
if (ctrl[0][j]) break; //马控制点及其列下面的点都是0；
f[0][j]=f[0][0];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if (ctrl[i][j])continue;
//如果这个点是控制点，那么跳过
f[i][j]=f[i][j-1]+f[i-1][j];
//从f[1][1]开始递推
}
cout<<f[n][m]; //输出答案.
return 0;
}